[{"file_date_updated":"2019-04-16T11:15:12Z","abstract":[{"text":"We prove three principal results. First we exhibit a drawing of $K_{10}$ in the plane for which there do not exist extensions of the edges to simple closed curves with any two curves intersecting at most twice. Second, we exhibit a drawing of $K_9$ that has an extension of its edges to simple closed curves such that any two curves intersect in at most two points, but no extension to simple closed curves has every two curves intersecting in exactly two points. Third, we show that every h-convex drawing (introduced by Arroyo et al, submitted) has extensions of its edges to simple closed curves such that any two curves intersect in exactly two points. Using this result, we show that} a set of three axioms of simple closed curve extensions characterizes h-convexity.","lang":"eng"}],"oa":1,"date_published":"2019-04-16T00:00:00Z","date_created":"2019-04-16T11:12:27Z","day":"16","publication_status":"draft","date_updated":"2019-08-02T12:39:17Z","accept":"1","month":"04","file":[{"content_type":"application/pdf","file_id":"6315","open_access":1,"access_level":"open_access","file_size":964688,"date_created":"2019-04-16T11:15:12Z","file_name":"2019_Draft_Arroyo.pdf","success":1,"date_updated":"2019-04-16T11:15:12Z","relation":"main_file","creator":"dernst"}],"page":"35","_id":"6313","ddc":["516"],"type":"preprint","project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"language":[{"iso":"eng"}],"citation":{"short":"A.M. Arroyo Guevara, B. Richter, M. Sunohara, (n.d.).","chicago":"Arroyo Guevara, Alan M, Bruce Richter, and Matthew Sunohara. “Extending Drawings of Complete Graphs into Arrangements of Pseudocircles,” n.d.","apa":"Arroyo Guevara, A. M., Richter, B., & Sunohara, M. (n.d.). Extending drawings of complete graphs into arrangements of pseudocircles.","mla":"Arroyo Guevara, Alan M., et al. *Extending Drawings of Complete Graphs into Arrangements of Pseudocircles*.","ama":"Arroyo Guevara AM, Richter B, Sunohara M. Extending drawings of complete graphs into arrangements of pseudocircles.","ista":"Arroyo Guevara AM, Richter B, Sunohara M. Extending drawings of complete graphs into arrangements of pseudocircles.","ieee":"A. M. Arroyo Guevara, B. Richter, and M. Sunohara, “Extending drawings of complete graphs into arrangements of pseudocircles.” ."},"year":"2019","status":"public","author":[{"last_name":"Arroyo Guevara","first_name":"Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","full_name":"Arroyo Guevara, Alan M"},{"full_name":"Richter, Bruce","first_name":"Bruce","last_name":"Richter"},{"full_name":"Sunohara, Matthew","last_name":"Sunohara","first_name":"Matthew"}],"oa_version":"Draft","department":[{"_id":"UlWa"}],"title":"Extending drawings of complete graphs into arrangements of pseudocircles","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"date_published":"2019-06-01T00:00:00Z","abstract":[{"text":"The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2.","lang":"eng"}],"file_date_updated":"2019-07-24T06:54:52Z","ddc":["000","510"],"file":[{"relation":"main_file","creator":"dernst","date_created":"2019-07-24T06:54:52Z","file_name":"2019_LIPICS_Fulek.pdf","success":1,"date_updated":"2019-07-24T06:54:52Z","file_id":"6667","open_access":1,"access_level":"open_access","file_size":559837,"content_type":"application/pdf"}],"alternative_title":["LIPIcs"],"page":"38:1-38:13","_id":"6647","date_updated":"2019-08-02T12:39:24Z","accept":"1","intvolume":" 129","date_created":"2019-07-17T10:35:04Z","day":"01","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771047"]},"project":[{"_id":"261FA626-B435-11E9-9278-68D0E5697425","name":"Eliminating intersections in drawings of graphs","grant_number":"M02281"}],"doi":"10.4230/LIPICS.SOCG.2019.38","title":"The crossing Tverberg theorem","cc_license":"'https://creativecommons.org/licenses/by/4.0/'","oa":1,"publication":"35th International Symposium on Computational Geometry","type":"conference","month":"06","publication_status":"published","year":"2019","status":"public","volume":129,"citation":{"ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. In: *35th International Symposium on Computational Geometry*. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:38:1-38:13. doi:10.4230/LIPICS.SOCG.2019.38","ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” in *35th International Symposium on Computational Geometry*, Portland, OR, United States, 2019, vol. 129, p. 38:1-38:13.","ista":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2019. The crossing Tverberg theorem. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium on Computational Geometry, LIPIcs, vol. 129. 38:1-38:13.","short":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13.","mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” *35th International Symposium on Computational Geometry*, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13, doi:10.4230/LIPICS.SOCG.2019.38.","apa":"Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2019). The crossing Tverberg theorem. In *35th International Symposium on Computational Geometry* (Vol. 129, p. 38:1-38:13). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.38","chicago":"Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” In *35th International Symposium on Computational Geometry*, 129:38:1-38:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.SOCG.2019.38."},"external_id":{"arxiv":["1812.04911"]},"conference":{"end_date":"2019-06-21","start_date":"2019-06-18","location":"Portland, OR, United States","name":"SoCG 2019: Symposium on Computational Geometry"},"quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"UlWa"}],"author":[{"last_name":"Fulek","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774"},{"last_name":"Gärtner","first_name":"Bernd","full_name":"Gärtner, Bernd"},{"full_name":"Kupavskii, Andrey","first_name":"Andrey","last_name":"Kupavskii"},{"full_name":"Valtr, Pavel","first_name":"Pavel","last_name":"Valtr"},{"last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568"}],"oa_version":"Published Version"},{"quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Lubiw","first_name":"Anna","full_name":"Lubiw, Anna"},{"last_name":"Masárová","first_name":"Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322"},{"last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568"}],"oa_version":"Published Version","department":[{"_id":"UlWa"}],"status":"public","year":"2019","volume":61,"external_id":{"arxiv":["1710.02741"]},"citation":{"ama":"Lubiw A, Masárová Z, Wagner U. A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations. *Discrete & Computational Geometry*. 2019;61(4):880-898. doi:10.1007/s00454-018-0035-8","ista":"Lubiw A, Masárová Z, Wagner U. 2019. A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations. Discrete & Computational Geometry. 61(4), 880–898.","ieee":"A. Lubiw, Z. Masárová, and U. Wagner, “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations,” *Discrete & Computational Geometry*, vol. 61, no. 4, pp. 880–898, 2019.","short":"A. Lubiw, Z. Masárová, U. Wagner, Discrete & Computational Geometry 61 (2019) 880–898.","mla":"Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” *Discrete & Computational Geometry*, vol. 61, no. 4, Springer Nature, 2019, pp. 880–98, doi:10.1007/s00454-018-0035-8.","apa":"Lubiw, A., Masárová, Z., & Wagner, U. (2019). A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations. *Discrete & Computational Geometry*, *61*(4), 880–898. https://doi.org/10.1007/s00454-018-0035-8","chicago":"Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” *Discrete & Computational Geometry* 61, no. 4 (2019): 880–98. https://doi.org/10.1007/s00454-018-0035-8."},"month":"06","type":"journal_article","article_type":"original","publication_status":"published","publication":"Discrete & Computational Geometry","title":"A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations","doi":"10.1007/s00454-018-0035-8","cc_license":"'https://creativecommons.org/licenses/by/4.0/'","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"683"}]},"publication_identifier":{"issn":["0179-5376","1432-0444"]},"project":[{"_id":"BFDF9788-01D1-11E9-AC17-EBD7A21D5664","name":"IST Austria Open Access Fund"}],"language":[{"iso":"eng"}],"publisher":"Springer Nature","file":[{"file_size":556276,"access_level":"open_access","file_id":"5988","open_access":1,"content_type":"application/pdf","relation":"main_file","creator":"dernst","success":1,"date_updated":"2019-02-14T11:57:22Z","date_created":"2019-02-14T11:57:22Z","file_name":"2018_DiscreteGeometry_Lubiw.pdf"}],"_id":"5986","page":"880-898","article_processing_charge":"No","ddc":["000"],"date_created":"2019-02-14T11:54:08Z","day":"01","intvolume":" 61","date_updated":"2019-09-24T07:18:40Z","accept":"1","date_published":"2019-06-01T00:00:00Z","abstract":[{"lang":"eng","text":"Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm (with 𝑂(𝑛8) being a crude bound on the run-time) to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of 𝑂(𝑛7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture."}],"file_date_updated":"2019-02-14T11:57:22Z","issue":"4"},{"related_material":{"record":[{"id":"6774","relation":"part_of_dissertation","status":"public"}]},"publication_identifier":{"issn":["2663-337X"]},"language":[{"iso":"eng"}],"publisher":"IST Austria","title":"Algorithmic aspects of homotopy theory and embeddability","doi":"10.15479/AT:ISTA:6681","cc_license":"'https://creativecommons.org/licenses/by/4.0/'","date_published":"2019-08-08T00:00:00Z","file_date_updated":"2019-08-08T06:41:37Z","abstract":[{"text":"The first part of the thesis considers the computational aspects of the homotopy groups πd(X) of a topological space X. It is well known that there is no algorithm to decide whether the fundamental group π1(X) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute the higher homotopy group πd(X) for any given d ≥ 2.\r\nHowever, these algorithms come with a caveat: They compute the isomorphism type of πd(X), d ≥ 2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πd(X). We present an algorithm that, given a simply connected space X, computes πd(X) and represents its elements as simplicial maps from suitable triangulations of the d-sphere Sd to X. For fixed d, the algorithm runs in time exponential in size(X), the number of simplices of X. Moreover, we prove that this is optimal: For every fixed d ≥ 2,\r\nwe construct a family of simply connected spaces X such that for any simplicial map representing a generator of πd(X), the size of the triangulation of S d on which the map is defined, is exponential in size(X).\r\nIn the second part of the thesis, we prove that the following question is algorithmically undecidable for d < ⌊3(k+1)/2⌋, k ≥ 5 and (k, d) ̸= (5, 7), which covers essentially everything outside the meta-stable range: Given a finite simplicial complex K of dimension k, decide whether there exists a piecewise-linear (i.e., linear on an arbitrarily fine subdivision of K) embedding f : K ↪→ Rd of K into a d-dimensional Euclidean space.","lang":"eng"}],"supervisor":[{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"alternative_title":["IST Austria Thesis"],"file":[{"file_id":"6771","open_access":1,"file_size":1464227,"access_level":"open_access","content_type":"application/pdf","relation":"main_file","request_a_copy":0,"creator":"szhechev","date_created":"2019-08-07T13:02:50Z","file_name":"Stephan_Zhechev_thesis.pdf","date_updated":"2019-08-07T13:02:50Z"},{"creator":"szhechev","request_a_copy":0,"relation":"source_file","file_name":"Stephan_Zhechev_thesis.tex","date_created":"2019-08-07T13:03:22Z","date_updated":"2019-08-08T06:41:37Z","open_access":0,"file_id":"6772","access_level":"closed","file_size":303988,"content_type":"application/octet-stream"},{"date_created":"2019-08-07T13:03:34Z","file_name":"supplementary_material.zip","date_updated":"2019-08-08T06:41:37Z","relation":"supplementary_material","request_a_copy":0,"creator":"szhechev","content_type":"application/zip","file_id":"6773","open_access":0,"access_level":"closed","file_size":1087004}],"page":"104","_id":"6681","ddc":["514"],"article_processing_charge":"No","date_created":"2019-07-26T11:14:34Z","day":"08","date_updated":"2019-09-27T08:48:09Z","accept":"1","status":"public","year":"2019","citation":{"apa":"Zhechev, S. Y. (2019). *Algorithmic aspects of homotopy theory and embeddability*. IST Austria. https://doi.org/10.15479/AT:ISTA:6681","mla":"Zhechev, Stephan Y. *Algorithmic Aspects of Homotopy Theory and Embeddability*. IST Austria, 2019, doi:10.15479/AT:ISTA:6681.","chicago":"Zhechev, Stephan Y. *Algorithmic Aspects of Homotopy Theory and Embeddability*. IST Austria, 2019. https://doi.org/10.15479/AT:ISTA:6681.","short":"S.Y. Zhechev, Algorithmic Aspects of Homotopy Theory and Embeddability, IST Austria, 2019.","ista":"Zhechev SY. 2019. Algorithmic aspects of homotopy theory and embeddability, IST Austria, 104p.","ieee":"S. Y. Zhechev, *Algorithmic aspects of homotopy theory and embeddability*. IST Austria, 2019.","ama":"Zhechev SY. *Algorithmic Aspects of Homotopy Theory and Embeddability*. IST Austria; 2019. doi:10.15479/AT:ISTA:6681"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"3AA52972-F248-11E8-B48F-1D18A9856A87","first_name":"Stephan Y","last_name":"Zhechev","full_name":"Zhechev, Stephan Y"}],"oa_version":"Published Version","department":[{"_id":"UlWa"}],"oa":1,"month":"08","type":"dissertation","publication_status":"published"},{"date_published":"2019-06-01T00:00:00Z","file_date_updated":"2019-06-12T06:45:33Z","abstract":[{"text":"Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined to be the minimum treewidth of the face pairing graph of any triangulation T of M. In this setting the relationship between the topology of a 3-manifold and its treewidth is of particular interest. First, as a corollary of work of Jaco and Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination with our earlier work with Wagner, this yields that for non-Haken manifolds the Heegaard genus and the treewidth are within a constant factor. Second, we characterize all 3-manifolds of treewidth one: These are precisely the lens spaces and a single other Seifert fibered space. Furthermore, we show that all remaining orientable Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth two. In particular, for every spherical 3-manifold we exhibit a triangulation of treewidth at most two. Our results further validate the parameter of treewidth (and other related parameters such as cutwidth or congestion) to be useful for topological computing, and also shed more light on the scope of existing FPT-algorithms in the field.","lang":"eng"}],"file":[{"file_name":"2019_LIPIcs-Huszar.pdf","date_created":"2019-06-12T06:45:33Z","date_updated":"2019-06-12T06:45:33Z","success":1,"creator":"kschuh","relation":"main_file","content_type":"application/pdf","open_access":1,"file_id":"6557","access_level":"open_access","file_size":905885}],"_id":"6556","page":"44:1-44:20","ddc":["516"],"date_created":"2019-06-11T20:09:57Z","day":"01","intvolume":" 129","accept":"1","date_updated":"2019-08-02T12:39:22Z","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","publication_identifier":{"isbn":["978-3-95977-104-7"],"issn":["1868-8969"]},"language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik","title":"3-manifold triangulations with small treewidth","doi":"10.4230/LIPIcs.SoCG.2019.44","cc_license":"'https://creativecommons.org/licenses/by/4.0/'","keyword":["computational 3-manifold topology","fixed-parameter tractability","layered triangulations","structural graph theory","treewidth","cutwidth","Heegaard genus"],"oa":1,"publication":"35th International Symposium on Computational Geometry (SoCG 2019)","month":"06","type":"conference","publication_status":"published","volume":129,"year":"2019","status":"public","external_id":{"arxiv":["1812.05528"]},"citation":{"ama":"Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: *35th International Symposium on Computational Geometry (SoCG 2019)*. Vol 129. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2019:44:1-44:20. doi:10.4230/LIPIcs.SoCG.2019.44","ieee":"K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,” in *35th International Symposium on Computational Geometry (SoCG 2019)*, Portland, Oregon, United States, 2019, vol. 129, p. 44:1-44:20.","ista":"Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth. 35th International Symposium on Computational Geometry (SoCG 2019). SoCG: Symposium on Computational GeometryLeibniz International Proceedings in Informatics (LIPIcs) vol. 129. 44:1-44:20.","short":"K. Huszár, J. Spreer, in:, 35th International Symposium on Computational Geometry (SoCG 2019), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019, p. 44:1-44:20.","mla":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” *35th International Symposium on Computational Geometry (SoCG 2019)*, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019, p. 44:1-44:20, doi:10.4230/LIPIcs.SoCG.2019.44.","apa":"Huszár, K., & Spreer, J. (2019). 3-manifold triangulations with small treewidth. In *35th International Symposium on Computational Geometry (SoCG 2019)* (Vol. 129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2019.44","chicago":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” In *35th International Symposium on Computational Geometry (SoCG 2019)*, 129:44:1-44:20. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019. https://doi.org/10.4230/LIPIcs.SoCG.2019.44."},"quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2019-06-18","end_date":"2019-06-21","location":"Portland, Oregon, United States","name":"SoCG: Symposium on Computational Geometry"},"author":[{"full_name":"Huszár, Kristóf","orcid":"0000-0002-5445-5057","last_name":"Huszár","id":"33C26278-F248-11E8-B48F-1D18A9856A87","first_name":"Kristóf"},{"full_name":"Spreer, Jonathan","first_name":"Jonathan","last_name":"Spreer"}],"oa_version":"Published Version","department":[{"_id":"UlWa"}]},{"project":[{"_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory","grant_number":"P31312"}],"publication_identifier":{"issn":["16153375"],"eissn":["16153383"]},"external_id":{"arxiv":["1312.2337"]},"publisher":"Springer Nature","language":[{"iso":"eng"}],"citation":{"ista":"Filakovský M, Vokřínek L. 2019. Are two given maps homotopic? An algorithmic viewpoint. Foundations of Computational Mathematics.","ieee":"M. Filakovský and L. Vokřínek, “Are two given maps homotopic? An algorithmic viewpoint,” *Foundations of Computational Mathematics*, 2019.","ama":"Filakovský M, Vokřínek L. Are two given maps homotopic? An algorithmic viewpoint. *Foundations of Computational Mathematics*. 2019. doi:10.1007/s10208-019-09419-x","apa":"Filakovský, M., & Vokřínek, L. (2019). Are two given maps homotopic? An algorithmic viewpoint. *Foundations of Computational Mathematics*. https://doi.org/10.1007/s10208-019-09419-x","mla":"Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An Algorithmic Viewpoint.” *Foundations of Computational Mathematics*, Springer Nature, 2019, doi:10.1007/s10208-019-09419-x.","chicago":"Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An Algorithmic Viewpoint.” *Foundations of Computational Mathematics*, 2019. https://doi.org/10.1007/s10208-019-09419-x.","short":"M. Filakovský, L. Vokřínek, Foundations of Computational Mathematics (2019)."},"status":"public","year":"2019","oa_version":"Preprint","main_file_link":[{"url":"https://arxiv.org/abs/1312.2337","open_access":"1"}],"author":[{"full_name":"Filakovský, Marek","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","last_name":"Filakovský"},{"first_name":"Lukas","last_name":"Vokřínek","full_name":"Vokřínek, Lukas"}],"department":[{"_id":"UlWa"}],"title":"Are two given maps homotopic? An algorithmic viewpoint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","doi":"10.1007/s10208-019-09419-x","abstract":[{"lang":"eng","text":"This paper presents two algorithms. The first decides the existence of a pointed homotopy between given simplicial maps 𝑓,𝑔:𝑋→𝑌, and the second computes the group [𝛴𝑋,𝑌]∗ of pointed homotopy classes of maps from a suspension; in both cases, the target Y is assumed simply connected. More generally, these algorithms work relative to 𝐴⊆𝑋."}],"oa":1,"publication":"Foundations of Computational Mathematics","date_published":"2019-05-29T00:00:00Z","day":"29","date_created":"2019-06-16T21:59:14Z","publication_status":"epub_ahead","date_updated":"2019-08-02T12:39:22Z","_id":"6563","month":"05","type":"journal_article"},{"main_file_link":[{"url":"https://arxiv.org/abs/1901.09955","open_access":"1"}],"author":[{"last_name":"Silva","first_name":"André ","full_name":"Silva, André "},{"full_name":"Arroyo Guevara, Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","first_name":"Alan M","last_name":"Arroyo Guevara"},{"full_name":"Richter, Bruce","last_name":"Richter","first_name":"Bruce"},{"last_name":"Lee","first_name":"Orlando","full_name":"Lee, Orlando"}],"oa_version":"Preprint","department":[{"_id":"UlWa"}],"quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Graphs with at most one crossing","doi":"10.1016/j.disc.2019.06.031","external_id":{"arxiv":["1901.09955"]},"project":[{"name":"Reglas de Conectividad funcional en el hipocampo","_id":"26366136-B435-11E9-9278-68D0E5697425"},{"name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}],"citation":{"short":"A. Silva, A.M. Arroyo Guevara, B. Richter, O. Lee, Discrete Mathematics (2019).","mla":"Silva, André, et al. “Graphs with at Most One Crossing.” *Discrete Mathematics*, Elsevier, 2019, doi:10.1016/j.disc.2019.06.031.","chicago":"Silva, André , Alan M Arroyo Guevara, Bruce Richter, and Orlando Lee. “Graphs with at Most One Crossing.” *Discrete Mathematics*, 2019. https://doi.org/10.1016/j.disc.2019.06.031.","apa":"Silva, A., Arroyo Guevara, A. M., Richter, B., & Lee, O. (2019). Graphs with at most one crossing. *Discrete Mathematics*. https://doi.org/10.1016/j.disc.2019.06.031","ama":"Silva A, Arroyo Guevara AM, Richter B, Lee O. Graphs with at most one crossing. *Discrete Mathematics*. 2019. doi:10.1016/j.disc.2019.06.031","ista":"Silva A, Arroyo Guevara AM, Richter B, Lee O. 2019. Graphs with at most one crossing. Discrete Mathematics.","ieee":"A. Silva, A. M. Arroyo Guevara, B. Richter, and O. Lee, “Graphs with at most one crossing,” *Discrete Mathematics*, 2019."},"language":[{"iso":"eng"}],"publisher":"Elsevier","status":"public","year":"2019","date_created":"2019-07-14T21:59:20Z","day":"03","date_updated":"2019-08-02T12:39:24Z","publication_status":"epub_ahead","month":"07","_id":"6638","type":"journal_article","abstract":[{"text":"The crossing number of a graph G is the least number of crossings over all possible drawings of G. We present a structural characterization of graphs with crossing number one.","lang":"eng"}],"oa":1,"publication":"Discrete Mathematics","date_published":"2019-07-03T00:00:00Z"},{"publication_identifier":{"issn":["0166218X"]},"project":[{"name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"433"}]},"publisher":"Elsevier","language":[{"iso":"eng"}],"citation":{"ama":"Fulek R, Pach J. Thrackles: An improved upper bound. *Discrete Applied Mathematics*. 2019;259(4):266-231. doi:10.1016/j.dam.2018.12.025","ista":"Fulek R, Pach J. 2019. Thrackles: An improved upper bound. Discrete Applied Mathematics. 259(4), 266–231.","ieee":"R. Fulek and J. Pach, “Thrackles: An improved upper bound,” *Discrete Applied Mathematics*, vol. 259, no. 4, pp. 266–231, 2019.","short":"R. Fulek, J. Pach, Discrete Applied Mathematics 259 (2019) 266–231.","mla":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” *Discrete Applied Mathematics*, vol. 259, no. 4, Elsevier, 2019, pp. 266–231, doi:10.1016/j.dam.2018.12.025.","chicago":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” *Discrete Applied Mathematics* 259, no. 4 (2019): 266–231. https://doi.org/10.1016/j.dam.2018.12.025.","apa":"Fulek, R., & Pach, J. (2019). Thrackles: An improved upper bound. *Discrete Applied Mathematics*, *259*(4), 266–231. https://doi.org/10.1016/j.dam.2018.12.025"},"year":"2019","status":"public","volume":259,"oa_version":"None","author":[{"last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774"},{"full_name":"Pach, János","last_name":"Pach","first_name":"János"}],"department":[{"_id":"UlWa"}],"title":"Thrackles: An improved upper bound","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","doi":"10.1016/j.dam.2018.12.025","abstract":[{"text":"A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an odd number of times. It is also shown that the maximum number of edges of a quasi-thrackle on n vertices is [Formula presented](n−1), and that this bound is best possible for infinitely many values of n.","lang":"eng"}],"publication":"Discrete Applied Mathematics","issue":"4","date_published":"2019-04-30T00:00:00Z","day":"30","date_created":"2019-01-20T22:59:17Z","date_updated":"2019-09-19T10:47:14Z","publication_status":"published","intvolume":" 259","_id":"5857","page":"266-231","month":"04","type":"journal_article"},{"date_created":"2018-12-11T11:45:05Z","day":"11","date_updated":"2019-08-02T12:37:28Z","intvolume":" 99","alternative_title":["LIPIcs"],"page":"401 - 4014","_id":"186","abstract":[{"lang":"eng","text":"A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The ℤ2-genus of a graph G is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective t × t grid or one of the following so-called t-Kuratowski graphs: K3, t, or t copies of K5 or K3,3 sharing at most 2 common vertices. We show that the ℤ2-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its ℤ2-genus, solving a problem posed by Schaefer and Štefankovič, and giving an approximate version of the Hanani-Tutte theorem on orientable surfaces."}],"date_published":"2018-06-11T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1803.05085","open_access":"1"}],"publist_id":"7734","title":"The ℤ2-Genus of Kuratowski minors","doi":"10.4230/LIPIcs.SoCG.2018.40","project":[{"name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281"}],"language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","month":"06","type":"conference","oa":1,"author":[{"last_name":"Fulek","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774"},{"full_name":"Kynčl, Jan","last_name":"Kynčl","first_name":"Jan"}],"oa_version":"Submitted Version","department":[{"_id":"UlWa"}],"quality_controlled":"1","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Budapest, Hungary","name":"SoCG: Symposium on Computational Geometry","end_date":"2018-06-14","start_date":"2018-06-11"},"external_id":{"arxiv":["1803.05085"]},"citation":{"ama":"Fulek R, Kynčl J. The ℤ2-Genus of Kuratowski minors. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:401-4014. doi:10.4230/LIPIcs.SoCG.2018.40","ieee":"R. Fulek and J. Kynčl, “The ℤ2-Genus of Kuratowski minors,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99, pp. 401–4014.","ista":"Fulek R, Kynčl J. 2018. The ℤ2-Genus of Kuratowski minors. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99. 401–4014.","short":"R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, pp. 401–4014.","mla":"Fulek, Radoslav, and Jan Kynčl. *The ℤ2-Genus of Kuratowski Minors*. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, pp. 401–4014, doi:10.4230/LIPIcs.SoCG.2018.40.","chicago":"Fulek, Radoslav, and Jan Kynčl. “The ℤ2-Genus of Kuratowski Minors,” 99:401–4014. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.40.","apa":"Fulek, R., & Kynčl, J. (2018). The ℤ2-Genus of Kuratowski minors (Vol. 99, pp. 401–4014). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.40"},"volume":99,"year":"2018","status":"public"},{"year":"2018","status":"public","publication_identifier":{"issn":["03649024"]},"project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme","grant_number":"291734"}],"external_id":{"arxiv":["1309.2399"]},"publisher":"Wiley","citation":{"short":"S. Chaplick, R. Fulek, P. Klavík, Journal of Graph Theory (2018).","chicago":"Chaplick, Steven, Radoslav Fulek, and Pavel Klavík. “Extending Partial Representations of Circle Graphs.” *Journal of Graph Theory*, 2018. https://doi.org/10.1002/jgt.22436.","apa":"Chaplick, S., Fulek, R., & Klavík, P. (2018). Extending partial representations of circle graphs. *Journal of Graph Theory*. https://doi.org/10.1002/jgt.22436","mla":"Chaplick, Steven, et al. “Extending Partial Representations of Circle Graphs.” *Journal of Graph Theory*, Wiley, 2018, doi:10.1002/jgt.22436.","ama":"Chaplick S, Fulek R, Klavík P. Extending partial representations of circle graphs. *Journal of Graph Theory*. 2018. doi:10.1002/jgt.22436","ieee":"S. Chaplick, R. Fulek, and P. Klavík, “Extending partial representations of circle graphs,” *Journal of Graph Theory*, 2018.","ista":"Chaplick S, Fulek R, Klavík P. 2018. Extending partial representations of circle graphs. Journal of Graph Theory."},"language":[{"iso":"eng"}],"title":"Extending partial representations of circle graphs","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","doi":"10.1002/jgt.22436","oa_version":"Preprint","main_file_link":[{"url":"https://arxiv.org/abs/1309.2399","open_access":"1"}],"author":[{"full_name":"Chaplick, Steven","first_name":"Steven","last_name":"Chaplick"},{"orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek"},{"full_name":"Klavík, Pavel","first_name":"Pavel","last_name":"Klavík"}],"department":[{"_id":"UlWa"}],"date_published":"2018-12-17T00:00:00Z","abstract":[{"lang":"eng","text":"The partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph G and a partial representation R′ giving some predrawn chords that represent an induced subgraph of G. The question is whether one can extend R′ to a representation R of the entire graph G, that is, whether one can draw the remaining chords into a partially predrawn representation to obtain a representation of G. Our main result is an O(n3) time algorithm for partial representation extension of circle graphs, where n is the number of vertices. To show this, we describe the structure of all representations of a circle graph using split decomposition. This can be of independent interest."}],"oa":1,"publication":"Journal of Graph Theory","_id":"5790","month":"12","type":"journal_article","day":"17","date_created":"2018-12-30T22:59:15Z","date_updated":"2019-08-02T12:39:04Z","publication_status":"epub_ahead"}]