[{"abstract":[{"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.","lang":"eng"}],"external_id":{"arxiv":["1309.2399"],"isi":["000485392800004"]},"publication_status":"published","volume":91,"quality_controlled":"1","department":[{"_id":"UlWa"}],"page":"365-394","date_published":"2019-08-01T00:00:00Z","publisher":"Wiley","project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734"}],"ec_funded":1,"citation":{"short":"S. Chaplick, R. Fulek, P. Klavík, Journal of Graph Theory 91 (2019) 365–394.","ieee":"S. Chaplick, R. Fulek, and P. Klavík, “Extending partial representations of circle graphs,” <i>Journal of Graph Theory</i>, vol. 91, no. 4. Wiley, pp. 365–394, 2019.","ama":"Chaplick S, Fulek R, Klavík P. Extending partial representations of circle graphs. <i>Journal of Graph Theory</i>. 2019;91(4):365-394. doi:<a href=\"https://doi.org/10.1002/jgt.22436\">10.1002/jgt.22436</a>","chicago":"Chaplick, Steven, Radoslav Fulek, and Pavel Klavík. “Extending Partial Representations of Circle Graphs.” <i>Journal of Graph Theory</i>. Wiley, 2019. <a href=\"https://doi.org/10.1002/jgt.22436\">https://doi.org/10.1002/jgt.22436</a>.","mla":"Chaplick, Steven, et al. “Extending Partial Representations of Circle Graphs.” <i>Journal of Graph Theory</i>, vol. 91, no. 4, Wiley, 2019, pp. 365–94, doi:<a href=\"https://doi.org/10.1002/jgt.22436\">10.1002/jgt.22436</a>.","ista":"Chaplick S, Fulek R, Klavík P. 2019. Extending partial representations of circle graphs. Journal of Graph Theory. 91(4), 365–394.","apa":"Chaplick, S., Fulek, R., &#38; Klavík, P. (2019). Extending partial representations of circle graphs. <i>Journal of Graph Theory</i>. Wiley. <a href=\"https://doi.org/10.1002/jgt.22436\">https://doi.org/10.1002/jgt.22436</a>"},"date_created":"2018-12-30T22:59:15Z","year":"2019","doi":"10.1002/jgt.22436","article_type":"original","_id":"5790","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1309.2399"}],"oa_version":"Preprint","day":"01","publication_identifier":{"issn":["03649024"]},"month":"08","arxiv":1,"author":[{"last_name":"Chaplick","full_name":"Chaplick, Steven","first_name":"Steven"},{"full_name":"Fulek, Radoslav","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","orcid":"0000-0001-8485-1774"},{"last_name":"Klavík","full_name":"Klavík, Pavel","first_name":"Pavel"}],"status":"public","type":"journal_article","intvolume":"        91","scopus_import":"1","isi":1,"title":"Extending partial representations of circle graphs","issue":"4","article_processing_charge":"No","oa":1,"date_updated":"2023-08-24T14:30:43Z","publication":"Journal of Graph Theory","language":[{"iso":"eng"}]},{"page":"266-231","department":[{"_id":"UlWa"}],"volume":259,"quality_controlled":"1","publisher":"Elsevier","date_published":"2019-04-30T00:00:00Z","project":[{"grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs"}],"external_id":{"isi":["000466061100020"],"arxiv":["1708.08037"]},"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_status":"published","doi":"10.1016/j.dam.2018.12.025","article_type":"original","_id":"5857","related_material":{"record":[{"id":"433","relation":"earlier_version","status":"public"}]},"date_created":"2019-01-20T22:59:17Z","citation":{"apa":"Fulek, R., &#38; Pach, J. (2019). Thrackles: An improved upper bound. <i>Discrete Applied Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.dam.2018.12.025\">https://doi.org/10.1016/j.dam.2018.12.025</a>","ieee":"R. Fulek and J. Pach, “Thrackles: An improved upper bound,” <i>Discrete Applied Mathematics</i>, vol. 259, no. 4. Elsevier, pp. 266–231, 2019.","ama":"Fulek R, Pach J. Thrackles: An improved upper bound. <i>Discrete Applied Mathematics</i>. 2019;259(4):266-231. doi:<a href=\"https://doi.org/10.1016/j.dam.2018.12.025\">10.1016/j.dam.2018.12.025</a>","short":"R. Fulek, J. Pach, Discrete Applied Mathematics 259 (2019) 266–231.","chicago":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” <i>Discrete Applied Mathematics</i>. Elsevier, 2019. <a href=\"https://doi.org/10.1016/j.dam.2018.12.025\">https://doi.org/10.1016/j.dam.2018.12.025</a>.","mla":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” <i>Discrete Applied Mathematics</i>, vol. 259, no. 4, Elsevier, 2019, pp. 266–231, doi:<a href=\"https://doi.org/10.1016/j.dam.2018.12.025\">10.1016/j.dam.2018.12.025</a>.","ista":"Fulek R, Pach J. 2019. Thrackles: An improved upper bound. Discrete Applied Mathematics. 259(4), 266–231."},"year":"2019","type":"journal_article","status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1708.08037"}],"oa_version":"Preprint","day":"30","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_identifier":{"issn":["0166218X"]},"month":"04","author":[{"first_name":"Radoslav","full_name":"Fulek, Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774"},{"full_name":"Pach, János","first_name":"János","last_name":"Pach"}],"arxiv":1,"publication":"Discrete Applied Mathematics","language":[{"iso":"eng"}],"intvolume":"       259","scopus_import":"1","isi":1,"title":"Thrackles: An improved upper bound","oa":1,"date_updated":"2023-08-24T14:39:33Z","issue":"4","article_processing_charge":"No"},{"related_material":{"record":[{"relation":"earlier_version","id":"683","status":"public"},{"relation":"dissertation_contains","id":"7944","status":"public"}]},"year":"2019","date_created":"2019-02-14T11:54:08Z","citation":{"chicago":"Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/s00454-018-0035-8\">https://doi.org/10.1007/s00454-018-0035-8</a>.","mla":"Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” <i>Discrete &#38; Computational Geometry</i>, vol. 61, no. 4, Springer Nature, 2019, pp. 880–98, doi:<a href=\"https://doi.org/10.1007/s00454-018-0035-8\">10.1007/s00454-018-0035-8</a>.","ista":"Lubiw A, Masárová Z, Wagner U. 2019. A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete &#38; Computational Geometry. 61(4), 880–898.","ama":"Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping edge-labelled triangulations. <i>Discrete &#38; Computational Geometry</i>. 2019;61(4):880-898. doi:<a href=\"https://doi.org/10.1007/s00454-018-0035-8\">10.1007/s00454-018-0035-8</a>","ieee":"A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for flipping edge-labelled triangulations,” <i>Discrete &#38; Computational Geometry</i>, vol. 61, no. 4. Springer Nature, pp. 880–898, 2019.","short":"A. Lubiw, Z. Masárová, U. Wagner, Discrete &#38; Computational Geometry 61 (2019) 880–898.","apa":"Lubiw, A., Masárová, Z., &#38; Wagner, U. (2019). A proof of the orbit conjecture for flipping edge-labelled triangulations. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-018-0035-8\">https://doi.org/10.1007/s00454-018-0035-8</a>"},"doi":"10.1007/s00454-018-0035-8","_id":"5986","article_type":"original","file_date_updated":"2020-07-14T12:47:14Z","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["000"],"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."}],"external_id":{"isi":["000466130000009"],"arxiv":["1710.02741"]},"publication_status":"published","date_published":"2019-06-01T00:00:00Z","publisher":"Springer Nature","quality_controlled":"1","volume":61,"page":"880-898","department":[{"_id":"UlWa"}],"project":[{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"isi":1,"intvolume":"        61","has_accepted_license":"1","scopus_import":"1","article_processing_charge":"Yes (via OA deal)","issue":"4","date_updated":"2023-09-07T13:17:36Z","oa":1,"title":"A proof of the orbit conjecture for flipping edge-labelled triangulations","publication":"Discrete & Computational Geometry","language":[{"iso":"eng"}],"month":"06","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","file":[{"access_level":"open_access","content_type":"application/pdf","relation":"main_file","file_size":556276,"creator":"dernst","date_updated":"2020-07-14T12:47:14Z","date_created":"2019-02-14T11:57:22Z","file_name":"2018_DiscreteGeometry_Lubiw.pdf","checksum":"e1bff88f1d77001b53b78c485ce048d7","file_id":"5988"}],"oa_version":"Published Version","day":"01","arxiv":1,"author":[{"full_name":"Lubiw, Anna","first_name":"Anna","last_name":"Lubiw"},{"orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","last_name":"Masárová","full_name":"Masárová, Zuzana","first_name":"Zuzana"},{"last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","first_name":"Uli"}],"status":"public","type":"journal_article"},{"date_updated":"2023-09-07T13:18:26Z","oa":1,"article_processing_charge":"No","title":"3-manifold triangulations with small treewidth","scopus_import":"1","has_accepted_license":"1","intvolume":"       129","language":[{"iso":"eng"}],"publication":"35th International Symposium on Computational Geometry","author":[{"full_name":"Huszár, Kristóf","first_name":"Kristóf","orcid":"0000-0002-5445-5057","last_name":"Huszár","id":"33C26278-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Spreer","full_name":"Spreer, Jonathan","first_name":"Jonathan"}],"arxiv":1,"conference":{"location":"Portland, Oregon, United States","end_date":"2019-06-21","name":"SoCG: Symposium on Computational Geometry","start_date":"2019-06-18"},"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-104-7"]},"month":"06","oa_version":"Published Version","day":"01","file":[{"date_created":"2019-06-12T06:45:33Z","date_updated":"2020-07-14T12:47:33Z","checksum":"29d18c435368468aa85823dabb157e43","file_id":"6557","file_name":"2019_LIPIcs-Huszar.pdf","file_size":905885,"content_type":"application/pdf","relation":"main_file","access_level":"open_access","creator":"kschuh"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LIPIcs"],"status":"public","type":"conference","year":"2019","date_created":"2019-06-11T20:09:57Z","citation":{"apa":"Huszár, K., &#38; Spreer, J. (2019). 3-manifold triangulations with small treewidth. In <i>35th International Symposium on Computational Geometry</i> (Vol. 129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2019.44\">https://doi.org/10.4230/LIPIcs.SoCG.2019.44</a>","mla":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” <i>35th International Symposium on Computational Geometry</i>, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2019.44\">10.4230/LIPIcs.SoCG.2019.44</a>.","chicago":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” In <i>35th International Symposium on Computational Geometry</i>, 129:44:1-44:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2019.44\">https://doi.org/10.4230/LIPIcs.SoCG.2019.44</a>.","ista":"Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth. 35th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 44:1-44:20.","short":"K. Huszár, J. Spreer, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20.","ama":"Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: <i>35th International Symposium on Computational Geometry</i>. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:44:1-44:20. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2019.44\">10.4230/LIPIcs.SoCG.2019.44</a>","ieee":"K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,” in <i>35th International Symposium on Computational Geometry</i>, Portland, Oregon, United States, 2019, vol. 129, p. 44:1-44:20."},"keyword":["computational 3-manifold topology","fixed-parameter tractability","layered triangulations","structural graph theory","treewidth","cutwidth","Heegaard genus"],"related_material":{"record":[{"relation":"part_of_dissertation","id":"8032","status":"public"}]},"file_date_updated":"2020-07-14T12:47:33Z","_id":"6556","doi":"10.4230/LIPIcs.SoCG.2019.44","publication_status":"published","ddc":["516"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"external_id":{"arxiv":["1812.05528"]},"abstract":[{"lang":"eng","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."}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2019-06-01T00:00:00Z","department":[{"_id":"UlWa"}],"page":"44:1-44:20","quality_controlled":"1","volume":129},{"publication":"Discrete Mathematics","language":[{"iso":"eng"}],"isi":1,"intvolume":"       342","scopus_import":"1","oa":1,"date_updated":"2023-08-29T06:31:41Z","issue":"11","article_processing_charge":"No","title":"Graphs with at most one crossing","status":"public","type":"journal_article","month":"11","publication_identifier":{"issn":["0012-365X"]},"oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1901.09955"}],"day":"01","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","author":[{"full_name":"Silva, André ","first_name":"André ","last_name":"Silva"},{"full_name":"Arroyo Guevara, Alan M","first_name":"Alan M","orcid":"0000-0003-2401-8670","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","last_name":"Arroyo Guevara"},{"full_name":"Richter, Bruce","first_name":"Bruce","last_name":"Richter"},{"last_name":"Lee","full_name":"Lee, Orlando","first_name":"Orlando"}],"arxiv":1,"doi":"10.1016/j.disc.2019.06.031","_id":"6638","ec_funded":1,"year":"2019","date_created":"2019-07-14T21:59:20Z","citation":{"apa":"Silva, A., Arroyo Guevara, A. M., Richter, B., &#38; Lee, O. (2019). Graphs with at most one crossing. <i>Discrete Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.disc.2019.06.031\">https://doi.org/10.1016/j.disc.2019.06.031</a>","mla":"Silva, André, et al. “Graphs with at Most One Crossing.” <i>Discrete Mathematics</i>, vol. 342, no. 11, Elsevier, 2019, pp. 3201–07, doi:<a href=\"https://doi.org/10.1016/j.disc.2019.06.031\">10.1016/j.disc.2019.06.031</a>.","ista":"Silva A, Arroyo Guevara AM, Richter B, Lee O. 2019. Graphs with at most one crossing. Discrete Mathematics. 342(11), 3201–3207.","chicago":"Silva, André , Alan M Arroyo Guevara, Bruce Richter, and Orlando Lee. “Graphs with at Most One Crossing.” <i>Discrete Mathematics</i>. Elsevier, 2019. <a href=\"https://doi.org/10.1016/j.disc.2019.06.031\">https://doi.org/10.1016/j.disc.2019.06.031</a>.","ama":"Silva A, Arroyo Guevara AM, Richter B, Lee O. Graphs with at most one crossing. <i>Discrete Mathematics</i>. 2019;342(11):3201-3207. doi:<a href=\"https://doi.org/10.1016/j.disc.2019.06.031\">10.1016/j.disc.2019.06.031</a>","ieee":"A. Silva, A. M. Arroyo Guevara, B. Richter, and O. Lee, “Graphs with at most one crossing,” <i>Discrete Mathematics</i>, vol. 342, no. 11. Elsevier, pp. 3201–3207, 2019.","short":"A. Silva, A.M. Arroyo Guevara, B. Richter, O. Lee, Discrete Mathematics 342 (2019) 3201–3207."},"publisher":"Elsevier","date_published":"2019-11-01T00:00:00Z","department":[{"_id":"UlWa"}],"page":"3201-3207","volume":342,"quality_controlled":"1","project":[{"_id":"26366136-B435-11E9-9278-68D0E5697425","name":"Reglas de Conectividad funcional en el hipocampo"},{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"}],"external_id":{"arxiv":["1901.09955"],"isi":["000486358100025"]},"abstract":[{"lang":"eng","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."}],"publication_status":"published"},{"alternative_title":["LIPIcs"],"type":"conference","status":"public","day":"01","oa_version":"Published Version","file":[{"date_created":"2019-07-24T06:54:52Z","date_updated":"2020-07-14T12:47:35Z","file_name":"2019_LIPICS_Fulek.pdf","checksum":"d6d017f8b41291b94d102294fa96ae9c","file_id":"6667","file_size":559837,"content_type":"application/pdf","relation":"main_file","access_level":"open_access","creator":"dernst"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"name":"SoCG 2019: Symposium on Computational Geometry","start_date":"2019-06-18","location":"Portland, OR, United States","end_date":"2019-06-21"},"publication_identifier":{"isbn":["9783959771047"],"issn":["1868-8969"]},"month":"06","author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","first_name":"Radoslav"},{"full_name":"Gärtner, Bernd","first_name":"Bernd","last_name":"Gärtner"},{"full_name":"Kupavskii, Andrey","first_name":"Andrey","last_name":"Kupavskii"},{"last_name":"Valtr","full_name":"Valtr, Pavel","first_name":"Pavel"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","first_name":"Uli"}],"arxiv":1,"publication":"35th International Symposium on Computational Geometry","language":[{"iso":"eng"}],"intvolume":"       129","scopus_import":1,"has_accepted_license":"1","title":"The crossing Tverberg theorem","date_updated":"2023-12-13T12:03:35Z","oa":1,"department":[{"_id":"UlWa"}],"page":"38:1-38:13","volume":129,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2019-06-01T00:00:00Z","project":[{"_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs"}],"external_id":{"arxiv":["1812.04911"]},"abstract":[{"lang":"eng","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."}],"ddc":["000","510"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publication_status":"published","doi":"10.4230/LIPICS.SOCG.2019.38","file_date_updated":"2020-07-14T12:47:35Z","_id":"6647","related_material":{"record":[{"id":"13974","relation":"later_version","status":"public"}]},"citation":{"apa":"Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., &#38; Wagner, U. (2019). The crossing Tverberg theorem. In <i>35th International Symposium on Computational Geometry</i> (Vol. 129, p. 38:1-38:13). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.38\">https://doi.org/10.4230/LIPICS.SOCG.2019.38</a>","chicago":"Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” In <i>35th International Symposium on Computational Geometry</i>, 129:38:1-38:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.38\">https://doi.org/10.4230/LIPICS.SOCG.2019.38</a>.","mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” <i>35th International Symposium on Computational Geometry</i>, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13, doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.38\">10.4230/LIPICS.SOCG.2019.38</a>.","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.","ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. In: <i>35th International Symposium on Computational Geometry</i>. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:38:1-38:13. doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.38\">10.4230/LIPICS.SOCG.2019.38</a>","ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” in <i>35th International Symposium on Computational Geometry</i>, Portland, OR, United States, 2019, vol. 129, p. 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."},"date_created":"2019-07-17T10:35:04Z","year":"2019"},{"doi":"10.15479/AT:ISTA:6681","_id":"6681","file_date_updated":"2020-07-14T12:47:37Z","related_material":{"record":[{"id":"6774","relation":"part_of_dissertation","status":"public"}]},"degree_awarded":"PhD","year":"2019","date_created":"2019-07-26T11:14:34Z","citation":{"apa":"Zhechev, S. Y. (2019). <i>Algorithmic aspects of homotopy theory and embeddability</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:6681\">https://doi.org/10.15479/AT:ISTA:6681</a>","ieee":"S. Y. Zhechev, “Algorithmic aspects of homotopy theory and embeddability,” Institute of Science and Technology Austria, 2019.","ama":"Zhechev SY. Algorithmic aspects of homotopy theory and embeddability. 2019. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:6681\">10.15479/AT:ISTA:6681</a>","short":"S.Y. Zhechev, Algorithmic Aspects of Homotopy Theory and Embeddability, Institute of Science and Technology Austria, 2019.","mla":"Zhechev, Stephan Y. <i>Algorithmic Aspects of Homotopy Theory and Embeddability</i>. Institute of Science and Technology Austria, 2019, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:6681\">10.15479/AT:ISTA:6681</a>.","chicago":"Zhechev, Stephan Y. “Algorithmic Aspects of Homotopy Theory and Embeddability.” Institute of Science and Technology Austria, 2019. <a href=\"https://doi.org/10.15479/AT:ISTA:6681\">https://doi.org/10.15479/AT:ISTA:6681</a>.","ista":"Zhechev SY. 2019. Algorithmic aspects of homotopy theory and embeddability. Institute of Science and Technology Austria."},"date_published":"2019-08-08T00:00:00Z","supervisor":[{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","full_name":"Wagner, Uli","first_name":"Uli"}],"publisher":"Institute of Science and Technology Austria","page":"104","department":[{"_id":"UlWa"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["514"],"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"}],"publication_status":"published","language":[{"iso":"eng"}],"has_accepted_license":"1","article_processing_charge":"No","date_updated":"2023-09-07T13:10:36Z","oa":1,"title":"Algorithmic aspects of homotopy theory and embeddability","status":"public","type":"dissertation","alternative_title":["ISTA Thesis"],"month":"08","publication_identifier":{"issn":["2663-337X"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","file":[{"creator":"szhechev","relation":"main_file","content_type":"application/pdf","access_level":"open_access","file_size":1464227,"file_id":"6771","checksum":"3231e7cbfca3b5687366f84f0a57a0c0","file_name":"Stephan_Zhechev_thesis.pdf","date_updated":"2020-07-14T12:47:37Z","date_created":"2019-08-07T13:02:50Z"},{"date_updated":"2020-07-14T12:47:37Z","date_created":"2019-08-07T13:03:22Z","file_name":"Stephan_Zhechev_thesis.tex","checksum":"85d65eb27b4377a9e332ee37a70f08b6","file_id":"6772","content_type":"application/octet-stream","access_level":"closed","relation":"source_file","file_size":303988,"creator":"szhechev"},{"date_updated":"2020-07-14T12:47:37Z","date_created":"2019-08-07T13:03:34Z","file_name":"supplementary_material.zip","checksum":"86b374d264ca2dd53e712728e253ee75","file_id":"6773","access_level":"closed","relation":"supplementary_material","content_type":"application/zip","file_size":1087004,"creator":"szhechev"}],"oa_version":"Published Version","day":"08","author":[{"last_name":"Zhechev","id":"3AA52972-F248-11E8-B48F-1D18A9856A87","full_name":"Zhechev, Stephan Y","first_name":"Stephan Y"}]},{"publication_status":"published","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["514","516"],"abstract":[{"text":"We give a detailed and easily accessible proof of Gromov’s Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map (Formula presented.) there exists a point (Formula presented.) that is contained in the images of a positive fraction (Formula presented.) of the d-cells of X. More generally, the conclusion holds if (Formula presented.) is replaced by any d-dimensional piecewise-linear manifold M, with a constant (Formula presented.) that depends only on d and on the expansion properties of X, but not on M.","lang":"eng"}],"external_id":{"isi":["000437122700017"]},"project":[{"name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","_id":"25FA3206-B435-11E9-9278-68D0E5697425","grant_number":"PP00P2_138948"}],"date_published":"2018-08-01T00:00:00Z","publisher":"Springer","quality_controlled":"1","volume":195,"page":"307–317","department":[{"_id":"UlWa"}],"year":"2018","publist_id":"6925","date_created":"2018-12-11T11:48:16Z","citation":{"ista":"Dotterrer D, Kaufman T, Wagner U. 2018. On expansion and topological overlap. Geometriae Dedicata. 195(1), 307–317.","mla":"Dotterrer, Dominic, et al. “On Expansion and Topological Overlap.” <i>Geometriae Dedicata</i>, vol. 195, no. 1, Springer, 2018, pp. 307–317, doi:<a href=\"https://doi.org/10.1007/s10711-017-0291-4\">10.1007/s10711-017-0291-4</a>.","chicago":"Dotterrer, Dominic, Tali Kaufman, and Uli Wagner. “On Expansion and Topological Overlap.” <i>Geometriae Dedicata</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s10711-017-0291-4\">https://doi.org/10.1007/s10711-017-0291-4</a>.","short":"D. Dotterrer, T. Kaufman, U. Wagner, Geometriae Dedicata 195 (2018) 307–317.","ama":"Dotterrer D, Kaufman T, Wagner U. On expansion and topological overlap. <i>Geometriae Dedicata</i>. 2018;195(1):307–317. doi:<a href=\"https://doi.org/10.1007/s10711-017-0291-4\">10.1007/s10711-017-0291-4</a>","ieee":"D. Dotterrer, T. Kaufman, and U. Wagner, “On expansion and topological overlap,” <i>Geometriae Dedicata</i>, vol. 195, no. 1. Springer, pp. 307–317, 2018.","apa":"Dotterrer, D., Kaufman, T., &#38; Wagner, U. (2018). On expansion and topological overlap. <i>Geometriae Dedicata</i>. Springer. <a href=\"https://doi.org/10.1007/s10711-017-0291-4\">https://doi.org/10.1007/s10711-017-0291-4</a>"},"related_material":{"record":[{"id":"1378","relation":"earlier_version","status":"public"}]},"_id":"742","file_date_updated":"2020-07-14T12:47:58Z","doi":"10.1007/s10711-017-0291-4","author":[{"last_name":"Dotterrer","first_name":"Dominic","full_name":"Dotterrer, Dominic"},{"full_name":"Kaufman, Tali","first_name":"Tali","last_name":"Kaufman"},{"full_name":"Wagner, Uli","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","orcid":"0000-0002-1494-0568"}],"month":"08","file":[{"file_name":"s10711-017-0291-4.pdf","checksum":"d2f70fc132156504aa4c626aa378a7ab","file_id":"5835","date_created":"2019-01-15T13:44:05Z","date_updated":"2020-07-14T12:47:58Z","creator":"kschuh","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_size":412486}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa_version":"Published Version","day":"01","type":"journal_article","status":"public","issue":"1","article_processing_charge":"Yes (via OA deal)","date_updated":"2023-09-27T12:29:57Z","oa":1,"pubrep_id":"912","title":"On expansion and topological overlap","isi":1,"has_accepted_license":"1","intvolume":"       195","scopus_import":"1","language":[{"iso":"eng"}],"publication":"Geometriae Dedicata"},{"oa":1,"date_updated":"2023-09-06T11:10:57Z","title":"Shellability is NP-complete","scopus_import":1,"has_accepted_license":"1","intvolume":"        99","language":[{"iso":"eng"}],"author":[{"full_name":"Goaoc, Xavier","first_name":"Xavier","last_name":"Goaoc"},{"full_name":"Paták, Pavel","first_name":"Pavel","last_name":"Paták"},{"last_name":"Patakova","id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683","full_name":"Patakova, Zuzana","first_name":"Zuzana"},{"orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","last_name":"Tancer","full_name":"Tancer, Martin","first_name":"Martin"},{"orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","first_name":"Uli"}],"conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2018-06-11","location":"Budapest, Hungary","end_date":"2018-06-14"},"month":"06","oa_version":"Published Version","day":"11","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"creator":"dernst","relation":"main_file","access_level":"open_access","file_size":718414,"content_type":"application/pdf","file_id":"5725","file_name":"2018_LIPIcs_Goaoc.pdf","checksum":"d12bdd60f04a57307867704b5f930afd","date_created":"2018-12-17T16:35:02Z","date_updated":"2020-07-14T12:45:18Z"}],"alternative_title":["Leibniz International Proceedings in Information, LIPIcs"],"status":"public","type":"conference","acknowledgement":"Partially supported by the project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM) of Czech-French collaboration.","year":"2018","citation":{"mla":"Goaoc, Xavier, et al. <i>Shellability Is NP-Complete</i>. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.41\">10.4230/LIPIcs.SoCG.2018.41</a>.","ista":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2018. Shellability is NP-complete. SoCG: Symposium on Computational Geometry, Leibniz International Proceedings in Information, LIPIcs, vol. 99, 41:1-41:16.","chicago":"Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Shellability Is NP-Complete,” 99:41:1-41:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.41\">https://doi.org/10.4230/LIPIcs.SoCG.2018.41</a>.","short":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16.","ama":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:41:1-41:16. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.41\">10.4230/LIPIcs.SoCG.2018.41</a>","ieee":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Shellability is NP-complete,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99, p. 41:1-41:16.","apa":"Goaoc, X., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2018). Shellability is NP-complete (Vol. 99, p. 41:1-41:16). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.41\">https://doi.org/10.4230/LIPIcs.SoCG.2018.41</a>"},"date_created":"2018-12-11T11:45:04Z","publist_id":"7736","related_material":{"record":[{"id":"7108","relation":"later_version","status":"public"}]},"file_date_updated":"2020-07-14T12:45:18Z","_id":"184","doi":"10.4230/LIPIcs.SoCG.2018.41","publication_status":"published","ddc":["516","000"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"abstract":[{"lang":"eng","text":"We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes."}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2018-06-11T00:00:00Z","department":[{"_id":"UlWa"}],"page":"41:1 - 41:16","quality_controlled":"1","volume":99},{"language":[{"iso":"eng"}],"scopus_import":1,"has_accepted_license":"1","intvolume":"        99","title":"Hanani-Tutte for approximating maps of graphs","oa":1,"date_updated":"2021-01-12T06:53:36Z","alternative_title":["Leibniz International Proceedings in Information, LIPIcs"],"status":"public","type":"conference","oa_version":"Published Version","day":"01","file":[{"access_level":"open_access","file_size":718857,"relation":"main_file","content_type":"application/pdf","creator":"dernst","date_created":"2018-12-17T12:33:52Z","date_updated":"2020-07-14T12:45:19Z","file_id":"5701","file_name":"2018_LIPIcs_Fulek.pdf","checksum":"f1b94f1a75b37c414a1f61d59fb2cd4c"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2018-06-11","location":"Budapest, Hungary","end_date":"2018-06-14"},"month":"01","publication_identifier":{"isbn":["978-3-95977-066-8"]},"author":[{"first_name":"Radoslav","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek"},{"first_name":"Jan","full_name":"Kynčl, Jan","last_name":"Kynčl"}],"doi":"10.4230/LIPIcs.SoCG.2018.39","file_date_updated":"2020-07-14T12:45:19Z","_id":"185","article_number":"39","publist_id":"7735","citation":{"apa":"Fulek, R., &#38; Kynčl, J. (2018). Hanani-Tutte for approximating maps of graphs (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.39\">https://doi.org/10.4230/LIPIcs.SoCG.2018.39</a>","chicago":"Fulek, Radoslav, and Jan Kynčl. “Hanani-Tutte for Approximating Maps of Graphs,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.39\">https://doi.org/10.4230/LIPIcs.SoCG.2018.39</a>.","mla":"Fulek, Radoslav, and Jan Kynčl. <i>Hanani-Tutte for Approximating Maps of Graphs</i>. Vol. 99, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.39\">10.4230/LIPIcs.SoCG.2018.39</a>.","ista":"Fulek R, Kynčl J. 2018. Hanani-Tutte for approximating maps of graphs. SoCG: Symposium on Computational Geometry, Leibniz International Proceedings in Information, LIPIcs, vol. 99, 39.","ieee":"R. Fulek and J. Kynčl, “Hanani-Tutte for approximating maps of graphs,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99.","ama":"Fulek R, Kynčl J. Hanani-Tutte for approximating maps of graphs. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.39\">10.4230/LIPIcs.SoCG.2018.39</a>","short":"R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018."},"date_created":"2018-12-11T11:45:04Z","year":"2018","department":[{"_id":"UlWa"}],"quality_controlled":"1","volume":99,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2018-01-01T00:00:00Z","project":[{"call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"abstract":[{"lang":"eng","text":"We resolve in the affirmative conjectures of A. Skopenkov and Repovš (1998), and M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the setting of approximating maps of graphs on 2-dimensional surfaces by embeddings. Our proof of this result is constructive and almost immediately implies an efficient algorithm for testing whether a given piecewise linear map of a graph in a surface is approximable by an embedding. More precisely, an instance of this problem consists of (i) a graph G whose vertices are partitioned into clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a region R of a 2-dimensional compact surface M given as the union of a set of pairwise disjoint discs corresponding to the clusters and a set of pairwise disjoint &quot;pipes&quot; corresponding to the bundles, connecting certain pairs of these discs. We are to decide whether G can be embedded inside M so that the vertices in every cluster are drawn in the corresponding disc, the edges in every bundle pass only through its corresponding pipe, and every edge crosses the boundary of each disc at most once."}],"ddc":["510"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publication_status":"published"},{"alternative_title":["LIPIcs"],"status":"public","type":"conference","author":[{"first_name":"Radoslav","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kynčl","full_name":"Kynčl, Jan","first_name":"Jan"}],"arxiv":1,"conference":{"end_date":"2018-06-14","location":"Budapest, Hungary","start_date":"2018-06-11","name":"SoCG: Symposium on Computational Geometry"},"month":"06","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1803.05085"}],"oa_version":"Submitted Version","day":"11","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"oa":1,"date_updated":"2023-08-14T12:43:51Z","article_processing_charge":"No","title":"The ℤ2-Genus of Kuratowski minors","scopus_import":"1","intvolume":"        99","project":[{"grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2018-06-11T00:00:00Z","page":"40.1 - 40.14","department":[{"_id":"UlWa"}],"quality_controlled":"1","volume":99,"publication_status":"published","external_id":{"arxiv":["1803.05085"]},"abstract":[{"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.","lang":"eng"}],"_id":"186","doi":"10.4230/LIPIcs.SoCG.2018.40","year":"2018","publist_id":"7734","citation":{"apa":"Fulek, R., &#38; Kynčl, J. (2018). The ℤ2-Genus of Kuratowski minors (Vol. 99, p. 40.1-40.14). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.40\">https://doi.org/10.4230/LIPIcs.SoCG.2018.40</a>","short":"R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 40.1-40.14.","ama":"Fulek R, Kynčl J. The ℤ2-Genus of Kuratowski minors. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:40.1-40.14. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.40\">10.4230/LIPIcs.SoCG.2018.40</a>","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, p. 40.1-40.14.","ista":"Fulek R, Kynčl J. 2018. The ℤ2-Genus of Kuratowski minors. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 40.1-40.14.","chicago":"Fulek, Radoslav, and Jan Kynčl. “The ℤ2-Genus of Kuratowski Minors,” 99:40.1-40.14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.40\">https://doi.org/10.4230/LIPIcs.SoCG.2018.40</a>.","mla":"Fulek, Radoslav, and Jan Kynčl. <i>The ℤ2-Genus of Kuratowski Minors</i>. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 40.1-40.14, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.40\">10.4230/LIPIcs.SoCG.2018.40</a>."},"date_created":"2018-12-11T11:45:05Z","related_material":{"record":[{"id":"11593","relation":"later_version","status":"public"}]}},{"isi":1,"scopus_import":"1","oa":1,"date_updated":"2023-09-11T12:49:55Z","article_processing_charge":"No","title":"Crossing minimization in perturbed drawings","language":[{"iso":"eng"}],"conference":{"location":"Barcelona, Spain","end_date":"2018-09-28","name":"Graph Drawing and Network Visualization","start_date":"2018-09-26"},"month":"12","publication_identifier":{"isbn":["9783030044138"]},"oa_version":"Preprint","day":"18","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1808.07608"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","first_name":"Radoslav","full_name":"Fulek, Radoslav"},{"last_name":"Tóth","full_name":"Tóth, Csaba D.","first_name":"Csaba D."}],"arxiv":1,"alternative_title":["LNCS"],"status":"public","type":"conference","year":"2018","citation":{"short":"R. Fulek, C.D. Tóth, in:, Springer, 2018, pp. 229–241.","ama":"Fulek R, Tóth CD. Crossing minimization in perturbed drawings. In: Vol 11282. Springer; 2018:229-241. doi:<a href=\"https://doi.org/10.1007/978-3-030-04414-5_16\">10.1007/978-3-030-04414-5_16</a>","ieee":"R. Fulek and C. D. Tóth, “Crossing minimization in perturbed drawings,” presented at the Graph Drawing and Network Visualization, Barcelona, Spain, 2018, vol. 11282, pp. 229–241.","mla":"Fulek, Radoslav, and Csaba D. Tóth. <i>Crossing Minimization in Perturbed Drawings</i>. Vol. 11282, Springer, 2018, pp. 229–41, doi:<a href=\"https://doi.org/10.1007/978-3-030-04414-5_16\">10.1007/978-3-030-04414-5_16</a>.","chicago":"Fulek, Radoslav, and Csaba D. Tóth. “Crossing Minimization in Perturbed Drawings,” 11282:229–41. Springer, 2018. <a href=\"https://doi.org/10.1007/978-3-030-04414-5_16\">https://doi.org/10.1007/978-3-030-04414-5_16</a>.","ista":"Fulek R, Tóth CD. 2018. Crossing minimization in perturbed drawings. Graph Drawing and Network Visualization, LNCS, vol. 11282, 229–241.","apa":"Fulek, R., &#38; Tóth, C. D. (2018). Crossing minimization in perturbed drawings (Vol. 11282, pp. 229–241). Presented at the Graph Drawing and Network Visualization, Barcelona, Spain: Springer. <a href=\"https://doi.org/10.1007/978-3-030-04414-5_16\">https://doi.org/10.1007/978-3-030-04414-5_16</a>"},"date_created":"2018-12-30T22:59:15Z","doi":"10.1007/978-3-030-04414-5_16","_id":"5791","external_id":{"arxiv":["1808.07608"],"isi":["000672802500016"]},"abstract":[{"text":"Due to data compression or low resolution, nearby vertices and edges of a graph drawing may be bundled to a common node or arc. We model such a “compromised” drawing by a piecewise linear map φ:G → ℝ. We wish to perturb φ by an arbitrarily small ε>0 into a proper drawing (in which the vertices are distinct points, any two edges intersect in finitely many points, and no three edges have a common interior point) that minimizes the number of crossings. An ε-perturbation, for every ε>0, is given by a piecewise linear map (Formula Presented), where with ||·|| is the uniform norm (i.e., sup norm). We present a polynomial-time solution for this optimization problem when G is a cycle and the map φ has no spurs (i.e., no two adjacent edges are mapped to overlapping arcs). We also show that the problem becomes NP-complete (i) when G is an arbitrary graph and φ has no spurs, and (ii) when φ may have spurs and G is a cycle or a union of disjoint paths.","lang":"eng"}],"publication_status":"published","publisher":"Springer","date_published":"2018-12-18T00:00:00Z","page":"229-241","department":[{"_id":"UlWa"}],"quality_controlled":"1","volume":"11282 "},{"day":"24","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1712.01341"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","month":"10","publication_identifier":{"eissn":["1741-3176"],"issn":["0278-3649"]},"author":[{"last_name":"Rohou","full_name":"Rohou, Simon","first_name":"Simon"},{"first_name":"Peter","full_name":"Franek, Peter","orcid":"0000-0001-8878-8397","id":"473294AE-F248-11E8-B48F-1D18A9856A87","last_name":"Franek"},{"first_name":"Clément","full_name":"Aubry, Clément","last_name":"Aubry"},{"last_name":"Jaulin","first_name":"Luc","full_name":"Jaulin, Luc"}],"arxiv":1,"status":"public","type":"journal_article","scopus_import":"1","intvolume":"        37","isi":1,"title":"Proving the existence of loops in robot trajectories","oa":1,"date_updated":"2023-09-19T10:41:59Z","article_processing_charge":"No","issue":"12","publication":"The International Journal of Robotics Research","language":[{"iso":"eng"}],"external_id":{"arxiv":["1712.01341"],"isi":["000456881100004"]},"abstract":[{"lang":"eng","text":"In this paper we present a reliable method to verify the existence of loops along the uncertain trajectory of a robot, based on proprioceptive measurements only, within a bounded-error context. The loop closure detection is one of the key points in simultaneous localization and mapping (SLAM) methods, especially in homogeneous environments with difficult scenes recognitions. The proposed approach is generic and could be coupled with conventional SLAM algorithms to reliably reduce their computing burden, thus improving the localization and mapping processes in the most challenging environments such as unexplored underwater extents. To prove that a robot performed a loop whatever the uncertainties in its evolution, we employ the notion of topological degree that originates in the field of differential topology. We show that a verification tool based on the topological degree is an optimal method for proving robot loops. This is demonstrated both on datasets from real missions involving autonomous underwater vehicles and by a mathematical discussion."}],"publication_status":"published","page":"1500-1516","department":[{"_id":"UlWa"}],"quality_controlled":"1","volume":37,"publisher":"SAGE Publications","date_published":"2018-10-24T00:00:00Z","citation":{"ieee":"S. Rohou, P. Franek, C. Aubry, and L. Jaulin, “Proving the existence of loops in robot trajectories,” <i>The International Journal of Robotics Research</i>, vol. 37, no. 12. SAGE Publications, pp. 1500–1516, 2018.","ama":"Rohou S, Franek P, Aubry C, Jaulin L. Proving the existence of loops in robot trajectories. <i>The International Journal of Robotics Research</i>. 2018;37(12):1500-1516. doi:<a href=\"https://doi.org/10.1177/0278364918808367\">10.1177/0278364918808367</a>","short":"S. Rohou, P. Franek, C. Aubry, L. Jaulin, The International Journal of Robotics Research 37 (2018) 1500–1516.","ista":"Rohou S, Franek P, Aubry C, Jaulin L. 2018. Proving the existence of loops in robot trajectories. The International Journal of Robotics Research. 37(12), 1500–1516.","mla":"Rohou, Simon, et al. “Proving the Existence of Loops in Robot Trajectories.” <i>The International Journal of Robotics Research</i>, vol. 37, no. 12, SAGE Publications, 2018, pp. 1500–16, doi:<a href=\"https://doi.org/10.1177/0278364918808367\">10.1177/0278364918808367</a>.","chicago":"Rohou, Simon, Peter Franek, Clément Aubry, and Luc Jaulin. “Proving the Existence of Loops in Robot Trajectories.” <i>The International Journal of Robotics Research</i>. SAGE Publications, 2018. <a href=\"https://doi.org/10.1177/0278364918808367\">https://doi.org/10.1177/0278364918808367</a>.","apa":"Rohou, S., Franek, P., Aubry, C., &#38; Jaulin, L. (2018). Proving the existence of loops in robot trajectories. <i>The International Journal of Robotics Research</i>. SAGE Publications. <a href=\"https://doi.org/10.1177/0278364918808367\">https://doi.org/10.1177/0278364918808367</a>"},"date_created":"2019-02-13T09:36:20Z","year":"2018","doi":"10.1177/0278364918808367","_id":"5960"},{"doi":"10.1017/fms.2018.7","_id":"6355","file_date_updated":"2020-07-14T12:47:28Z","article_number":"e7","related_material":{"record":[{"relation":"dissertation_contains","id":"8156","status":"public"}]},"ec_funded":1,"year":"2018","date_created":"2019-04-30T06:09:57Z","citation":{"apa":"Akopyan, A., &#38; Avvakumov, S. (2018). Any cyclic quadrilateral can be inscribed in any closed convex smooth curve. <i>Forum of Mathematics, Sigma</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/fms.2018.7\">https://doi.org/10.1017/fms.2018.7</a>","ieee":"A. Akopyan and S. Avvakumov, “Any cyclic quadrilateral can be inscribed in any closed convex smooth curve,” <i>Forum of Mathematics, Sigma</i>, vol. 6. Cambridge University Press, 2018.","ama":"Akopyan A, Avvakumov S. Any cyclic quadrilateral can be inscribed in any closed convex smooth curve. <i>Forum of Mathematics, Sigma</i>. 2018;6. doi:<a href=\"https://doi.org/10.1017/fms.2018.7\">10.1017/fms.2018.7</a>","short":"A. Akopyan, S. Avvakumov, Forum of Mathematics, Sigma 6 (2018).","mla":"Akopyan, Arseniy, and Sergey Avvakumov. “Any Cyclic Quadrilateral Can Be Inscribed in Any Closed Convex Smooth Curve.” <i>Forum of Mathematics, Sigma</i>, vol. 6, e7, Cambridge University Press, 2018, doi:<a href=\"https://doi.org/10.1017/fms.2018.7\">10.1017/fms.2018.7</a>.","chicago":"Akopyan, Arseniy, and Sergey Avvakumov. “Any Cyclic Quadrilateral Can Be Inscribed in Any Closed Convex Smooth Curve.” <i>Forum of Mathematics, Sigma</i>. Cambridge University Press, 2018. <a href=\"https://doi.org/10.1017/fms.2018.7\">https://doi.org/10.1017/fms.2018.7</a>.","ista":"Akopyan A, Avvakumov S. 2018. Any cyclic quadrilateral can be inscribed in any closed convex smooth curve. Forum of Mathematics, Sigma. 6, e7."},"date_published":"2018-05-31T00:00:00Z","publisher":"Cambridge University Press","volume":6,"quality_controlled":"1","department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"JaMa"}],"project":[{"_id":"256E75B8-B435-11E9-9278-68D0E5697425","grant_number":"716117","call_identifier":"H2020","name":"Optimal Transport and Stochastic Dynamics"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["510"],"abstract":[{"text":"We  prove  that  any  cyclic  quadrilateral  can  be  inscribed  in  any  closed  convex C1-curve.  The smoothness condition is not required if the quadrilateral is a rectangle.","lang":"eng"}],"external_id":{"arxiv":["1712.10205"],"isi":["000433915500001"]},"publication_status":"published","publication":"Forum of Mathematics, Sigma","language":[{"iso":"eng"}],"isi":1,"intvolume":"         6","has_accepted_license":"1","article_processing_charge":"No","date_updated":"2023-09-19T14:50:12Z","oa":1,"title":"Any cyclic quadrilateral can be inscribed in any closed convex smooth curve","status":"public","type":"journal_article","month":"05","publication_identifier":{"issn":["2050-5094"]},"file":[{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_size":249246,"creator":"dernst","date_updated":"2020-07-14T12:47:28Z","date_created":"2019-04-30T06:14:58Z","file_id":"6356","file_name":"2018_ForumMahtematics_Akopyan.pdf","checksum":"5a71b24ba712a3eb2e46165a38fbc30a"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","day":"31","oa_version":"Published Version","arxiv":1,"author":[{"first_name":"Arseniy","full_name":"Akopyan, Arseniy","id":"430D2C90-F248-11E8-B48F-1D18A9856A87","last_name":"Akopyan","orcid":"0000-0002-2548-617X"},{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","last_name":"Avvakumov","full_name":"Avvakumov, Sergey","first_name":"Sergey"}]},{"project":[{"call_identifier":"FWF","name":"Robust invariants of Nonlinear Systems","grant_number":"M01980","_id":"25F8B9BC-B435-11E9-9278-68D0E5697425"},{"name":"FWF Open Access Fund","call_identifier":"FWF","_id":"3AC91DDA-15DF-11EA-824D-93A3E7B544D1"}],"quality_controlled":"1","volume":2,"page":"177-231","department":[{"_id":"UlWa"}],"date_published":"2018-12-01T00:00:00Z","publisher":"Springer","publication_status":"published","abstract":[{"text":"A central problem of algebraic topology is to understand the homotopy groups  𝜋𝑑(𝑋)  of a topological space X. For the computational version of the problem, it is well known that there is no algorithm to decide whether the fundamental group  𝜋1(𝑋)  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(𝑋)  trivial), compute the higher homotopy group   𝜋𝑑(𝑋)  for any given   𝑑≥2 . However, these algorithms come with a caveat: They compute the isomorphism type of   𝜋𝑑(𝑋) ,   𝑑≥2  as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of   𝜋𝑑(𝑋) . Converting elements of this abstract group into explicit geometric maps from the d-dimensional sphere   𝑆𝑑  to X has been one of the main unsolved problems in the emerging field of computational homotopy theory. Here we present an algorithm that, given a simply connected space X, computes   𝜋𝑑(𝑋)  and represents its elements as simplicial maps from a suitable triangulation of the d-sphere   𝑆𝑑  to X. For fixed d, the algorithm runs in time exponential in   size(𝑋) , the number of simplices of X. Moreover, we prove that this is optimal: For every fixed   𝑑≥2 , we construct a family of simply connected spaces X such that for any simplicial map representing a generator of   𝜋𝑑(𝑋) , the size of the triangulation of   𝑆𝑑  on which the map is defined, is exponential in size(𝑋) .","lang":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["514"],"_id":"6774","article_type":"original","file_date_updated":"2020-07-14T12:47:40Z","doi":"10.1007/s41468-018-0021-5","citation":{"ieee":"M. Filakovský, P. Franek, U. Wagner, and S. Y. Zhechev, “Computing simplicial representatives of homotopy group elements,” <i>Journal of Applied and Computational Topology</i>, vol. 2, no. 3–4. Springer, pp. 177–231, 2018.","ama":"Filakovský M, Franek P, Wagner U, Zhechev SY. Computing simplicial representatives of homotopy group elements. <i>Journal of Applied and Computational Topology</i>. 2018;2(3-4):177-231. doi:<a href=\"https://doi.org/10.1007/s41468-018-0021-5\">10.1007/s41468-018-0021-5</a>","short":"M. Filakovský, P. Franek, U. Wagner, S.Y. Zhechev, Journal of Applied and Computational Topology 2 (2018) 177–231.","chicago":"Filakovský, Marek, Peter Franek, Uli Wagner, and Stephan Y Zhechev. “Computing Simplicial Representatives of Homotopy Group Elements.” <i>Journal of Applied and Computational Topology</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s41468-018-0021-5\">https://doi.org/10.1007/s41468-018-0021-5</a>.","mla":"Filakovský, Marek, et al. “Computing Simplicial Representatives of Homotopy Group Elements.” <i>Journal of Applied and Computational Topology</i>, vol. 2, no. 3–4, Springer, 2018, pp. 177–231, doi:<a href=\"https://doi.org/10.1007/s41468-018-0021-5\">10.1007/s41468-018-0021-5</a>.","ista":"Filakovský M, Franek P, Wagner U, Zhechev SY. 2018. Computing simplicial representatives of homotopy group elements. Journal of Applied and Computational Topology. 2(3–4), 177–231.","apa":"Filakovský, M., Franek, P., Wagner, U., &#38; Zhechev, S. Y. (2018). Computing simplicial representatives of homotopy group elements. <i>Journal of Applied and Computational Topology</i>. Springer. <a href=\"https://doi.org/10.1007/s41468-018-0021-5\">https://doi.org/10.1007/s41468-018-0021-5</a>"},"date_created":"2019-08-08T06:47:40Z","year":"2018","related_material":{"record":[{"status":"public","id":"6681","relation":"dissertation_contains"}]},"type":"journal_article","status":"public","author":[{"id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","last_name":"Filakovský","first_name":"Marek","full_name":"Filakovský, Marek"},{"orcid":"0000-0001-8878-8397","id":"473294AE-F248-11E8-B48F-1D18A9856A87","last_name":"Franek","first_name":"Peter","full_name":"Franek, Peter"},{"first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Zhechev, Stephan Y","first_name":"Stephan Y","id":"3AA52972-F248-11E8-B48F-1D18A9856A87","last_name":"Zhechev"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"creator":"dernst","file_size":1056278,"content_type":"application/pdf","relation":"main_file","access_level":"open_access","checksum":"cf9e7fcd2a113dd4828774fc75cdb7e8","file_name":"2018_JourAppliedComputTopology_Filakovsky.pdf","file_id":"6775","date_updated":"2020-07-14T12:47:40Z","date_created":"2019-08-08T06:55:21Z"}],"day":"01","oa_version":"Published Version","month":"12","publication_identifier":{"issn":["2367-1726"],"eissn":["2367-1734"]},"language":[{"iso":"eng"}],"publication":"Journal of Applied and Computational Topology","title":"Computing simplicial representatives of homotopy group elements","issue":"3-4","oa":1,"date_updated":"2023-09-07T13:10:36Z","has_accepted_license":"1","intvolume":"         2"},{"alternative_title":["LIPIcs"],"status":"public","type":"conference","conference":{"location":"Budapest, Hungary","end_date":"2018-06-14","name":"SoCG: Symposium on Computational Geometry","start_date":"2018-06-11"},"month":"06","publication_identifier":{"issn":["18688969"]},"oa_version":"Submitted Version","day":"01","file":[{"checksum":"530d084116778135d5bffaa317479cac","file_id":"5713","file_name":"2018_LIPIcs_Huszar.pdf","date_created":"2018-12-17T15:32:38Z","date_updated":"2020-07-14T12:45:51Z","creator":"dernst","content_type":"application/pdf","access_level":"open_access","file_size":642522,"relation":"main_file"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Kristóf","full_name":"Huszár, Kristóf","id":"33C26278-F248-11E8-B48F-1D18A9856A87","last_name":"Huszár","orcid":"0000-0002-5445-5057"},{"first_name":"Jonathan","full_name":"Spreer, Jonathan","last_name":"Spreer"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","full_name":"Wagner, Uli","first_name":"Uli"}],"arxiv":1,"language":[{"iso":"eng"}],"has_accepted_license":"1","intvolume":"        99","scopus_import":1,"oa":1,"date_updated":"2023-09-06T11:13:41Z","article_processing_charge":"No","title":"On the treewidth of triangulated 3-manifolds","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2018-06-01T00:00:00Z","department":[{"_id":"UlWa"}],"volume":99,"quality_controlled":"1","ddc":["516","000"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"external_id":{"arxiv":["1712.00434"]},"abstract":[{"lang":"eng","text":"In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how &quot;simple&quot; or &quot;thin&quot; a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth. In view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs). We derive these results from work of Agol and of Scharlemann and Thompson, by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 48(k+1) (resp. 4(3k+1))."}],"publication_status":"published","doi":"10.4230/LIPIcs.SoCG.2018.46","file_date_updated":"2020-07-14T12:45:51Z","_id":"285","article_number":"46","related_material":{"record":[{"id":"7093","relation":"later_version","status":"public"}]},"acknowledgement":"Research of the second author was supported by the Einstein Foundation (project “Einstein Visiting Fellow Santos”) and by the Simons Foundation (“Simons Visiting Professors” program).","year":"2018","citation":{"apa":"Huszár, K., Spreer, J., &#38; Wagner, U. (2018). On the treewidth of triangulated 3-manifolds (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.46\">https://doi.org/10.4230/LIPIcs.SoCG.2018.46</a>","ista":"Huszár K, Spreer J, Wagner U. 2018. On the treewidth of triangulated 3-manifolds. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 46.","chicago":"Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.46\">https://doi.org/10.4230/LIPIcs.SoCG.2018.46</a>.","mla":"Huszár, Kristóf, et al. <i>On the Treewidth of Triangulated 3-Manifolds</i>. Vol. 99, 46, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.46\">10.4230/LIPIcs.SoCG.2018.46</a>.","ieee":"K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99.","ama":"Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.46\">10.4230/LIPIcs.SoCG.2018.46</a>","short":"K. Huszár, J. Spreer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018."},"date_created":"2018-12-11T11:45:37Z","publist_id":"7614"},{"doi":"10.1137/1.9781611975031.20","_id":"309","related_material":{"record":[{"relation":"later_version","id":"6982","status":"public"}]},"date_created":"2018-12-11T11:45:45Z","publist_id":"7556","citation":{"apa":"Akitaya, H., Fulek, R., &#38; Tóth, C. (2018). Recognizing weak embeddings of graphs (pp. 274–292). Presented at the SODA: Symposium on Discrete Algorithms, New Orleans, LA, USA: ACM. <a href=\"https://doi.org/10.1137/1.9781611975031.20\">https://doi.org/10.1137/1.9781611975031.20</a>","ama":"Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. In: ACM; 2018:274-292. doi:<a href=\"https://doi.org/10.1137/1.9781611975031.20\">10.1137/1.9781611975031.20</a>","ieee":"H. Akitaya, R. Fulek, and C. Tóth, “Recognizing weak embeddings of graphs,” presented at the SODA: Symposium on Discrete Algorithms, New Orleans, LA, USA, 2018, pp. 274–292.","short":"H. Akitaya, R. Fulek, C. Tóth, in:, ACM, 2018, pp. 274–292.","chicago":"Akitaya, Hugo, Radoslav Fulek, and Csaba Tóth. “Recognizing Weak Embeddings of Graphs,” 274–92. ACM, 2018. <a href=\"https://doi.org/10.1137/1.9781611975031.20\">https://doi.org/10.1137/1.9781611975031.20</a>.","mla":"Akitaya, Hugo, et al. <i>Recognizing Weak Embeddings of Graphs</i>. ACM, 2018, pp. 274–92, doi:<a href=\"https://doi.org/10.1137/1.9781611975031.20\">10.1137/1.9781611975031.20</a>.","ista":"Akitaya H, Fulek R, Tóth C. 2018. Recognizing weak embeddings of graphs. SODA: Symposium on Discrete Algorithms, 274–292."},"year":"2018","acknowledgement":"∗Research supported in part by the NSF awards CCF-1422311 and CCF-1423615, and the Science Without Borders program. The second author gratefully acknowledges support from Austrian Science Fund (FWF): M2281-N35.","quality_controlled":"1","page":"274 - 292","department":[{"_id":"UlWa"}],"date_published":"2018-01-01T00:00:00Z","publisher":"ACM","project":[{"call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"abstract":[{"lang":"eng","text":"We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding ' : G ! M of a graph G into a 2manifold M maps the vertices in V (G) to distinct points and the edges in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to a common node or arc, due to data compression or low resolution. This raises the computational problem of deciding whether a given map ' : G ! M comes from an embedding. A map ' : G ! M is a weak embedding if it can be perturbed into an embedding ψ: G ! M with k' \"k < \" for every &quot; &gt; 0. A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kyncl [14], which reduces to solving a system of linear equations over Z2. It runs in O(n2!) O(n4:75) time, where 2:373 is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O(n log n). Our algorithm is also conceptually simpler than [14]: We perform a sequence of local operations that gradually &quot;untangles&quot; the image '(G) into an embedding (G), or reports that ' is not a weak embedding. It generalizes a recent technique developed for the case that G is a cycle and the embedding is a simple polygon [1], and combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations."}],"external_id":{"isi":["000483921200021"],"arxiv":["1709.09209"]},"publication_status":"published","language":[{"iso":"eng"}],"scopus_import":"1","isi":1,"title":"Recognizing weak embeddings of graphs","article_processing_charge":"No","oa":1,"date_updated":"2023-09-15T12:19:32Z","type":"conference","status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","day":"01","main_file_link":[{"url":"https://arxiv.org/abs/1709.09209","open_access":"1"}],"oa_version":"Preprint","month":"01","conference":{"name":"SODA: Symposium on Discrete Algorithms","start_date":"2018-01-07","location":"New Orleans, LA, USA","end_date":"2018-01-10"},"arxiv":1,"author":[{"last_name":"Akitaya","first_name":"Hugo","full_name":"Akitaya, Hugo"},{"last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","first_name":"Radoslav"},{"first_name":"Csaba","full_name":"Tóth, Csaba","last_name":"Tóth"}]},{"doi":"10.1145/3078632","_id":"425","article_type":"original","related_material":{"record":[{"status":"public","id":"2157","relation":"earlier_version"}]},"article_number":"5","ec_funded":1,"date_created":"2018-12-11T11:46:24Z","publist_id":"7398","citation":{"apa":"Matoušek, J., Sedgwick, E., Tancer, M., &#38; Wagner, U. (2018). Embeddability in the 3-Sphere is decidable. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/3078632\">https://doi.org/10.1145/3078632</a>","chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Embeddability in the 3-Sphere Is Decidable.” <i>Journal of the ACM</i>. ACM, 2018. <a href=\"https://doi.org/10.1145/3078632\">https://doi.org/10.1145/3078632</a>.","mla":"Matoušek, Jiří, et al. “Embeddability in the 3-Sphere Is Decidable.” <i>Journal of the ACM</i>, vol. 65, no. 1, 5, ACM, 2018, doi:<a href=\"https://doi.org/10.1145/3078632\">10.1145/3078632</a>.","ista":"Matoušek J, Sedgwick E, Tancer M, Wagner U. 2018. Embeddability in the 3-Sphere is decidable. Journal of the ACM. 65(1), 5.","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Embeddability in the 3-Sphere is decidable,” <i>Journal of the ACM</i>, vol. 65, no. 1. ACM, 2018.","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Embeddability in the 3-Sphere is decidable. <i>Journal of the ACM</i>. 2018;65(1). doi:<a href=\"https://doi.org/10.1145/3078632\">10.1145/3078632</a>","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Journal of the ACM 65 (2018)."},"year":"2018","volume":65,"quality_controlled":"1","department":[{"_id":"UlWa"}],"date_published":"2018-01-01T00:00:00Z","publisher":"ACM","project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734"}],"abstract":[{"text":"We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in R3? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which allows us to simplify X and recurse, is in proving that if X can be embedded in S3, then there is also an embedding in which X has a short meridian, that is, an essential curve in the boundary of X bounding a disk in S3 \\ X with length bounded by a computable function of the number of tetrahedra of X.","lang":"eng"}],"external_id":{"arxiv":["1402.0815"],"isi":["000425685900006"]},"publication_status":"published","publication":"Journal of the ACM","language":[{"iso":"eng"}],"intvolume":"        65","scopus_import":"1","isi":1,"title":"Embeddability in the 3-Sphere is decidable","issue":"1","article_processing_charge":"No","date_updated":"2023-09-11T13:38:49Z","oa":1,"type":"journal_article","status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","day":"01","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1402.0815"}],"month":"01","arxiv":1,"author":[{"last_name":"Matoušek","full_name":"Matoušek, Jiří","first_name":"Jiří"},{"full_name":"Sedgwick, Eric","first_name":"Eric","last_name":"Sedgwick"},{"orcid":"0000-0002-1191-6714","last_name":"Tancer","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","full_name":"Tancer, Martin","first_name":"Martin"},{"last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","full_name":"Wagner, Uli"}]},{"intvolume":"     10692","scopus_import":1,"oa":1,"date_updated":"2023-08-24T14:39:32Z","title":"Thrackles: An improved upper bound","language":[{"iso":"eng"}],"month":"01","conference":{"end_date":"2017-09-27","location":"Boston, MA, United States","start_date":"201-09-25","name":"GD 2017: Graph Drawing and Network Visualization"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1708.08037"}],"day":"21","oa_version":"Submitted Version","arxiv":1,"author":[{"orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","full_name":"Fulek, Radoslav","first_name":"Radoslav"},{"last_name":"Pach","first_name":"János","full_name":"Pach, János"}],"status":"public","type":"conference","alternative_title":["LNCS"],"related_material":{"record":[{"relation":"later_version","id":"5857","status":"public"}]},"year":"2018","date_created":"2018-12-11T11:46:27Z","publist_id":"7390","citation":{"apa":"Fulek, R., &#38; Pach, J. (2018). Thrackles: An improved upper bound (Vol. 10692, pp. 160–166). Presented at the GD 2017: Graph Drawing and Network Visualization, Boston, MA, United States: Springer. <a href=\"https://doi.org/10.1007/978-3-319-73915-1_14\">https://doi.org/10.1007/978-3-319-73915-1_14</a>","ama":"Fulek R, Pach J. Thrackles: An improved upper bound. In: Vol 10692. Springer; 2018:160-166. doi:<a href=\"https://doi.org/10.1007/978-3-319-73915-1_14\">10.1007/978-3-319-73915-1_14</a>","ieee":"R. Fulek and J. Pach, “Thrackles: An improved upper bound,” presented at the GD 2017: Graph Drawing and Network Visualization, Boston, MA, United States, 2018, vol. 10692, pp. 160–166.","short":"R. Fulek, J. Pach, in:, Springer, 2018, pp. 160–166.","mla":"Fulek, Radoslav, and János Pach. <i>Thrackles: An Improved Upper Bound</i>. Vol. 10692, Springer, 2018, pp. 160–66, doi:<a href=\"https://doi.org/10.1007/978-3-319-73915-1_14\">10.1007/978-3-319-73915-1_14</a>.","chicago":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound,” 10692:160–66. Springer, 2018. <a href=\"https://doi.org/10.1007/978-3-319-73915-1_14\">https://doi.org/10.1007/978-3-319-73915-1_14</a>.","ista":"Fulek R, Pach J. 2018. Thrackles: An improved upper bound. GD 2017: Graph Drawing and Network Visualization, LNCS, vol. 10692, 160–166."},"doi":"10.1007/978-3-319-73915-1_14","_id":"433","abstract":[{"lang":"eng","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 3/2(n-1), and that this bound is best possible for infinitely many values of n."}],"external_id":{"arxiv":["1708.08037"]},"publication_status":"published","date_published":"2018-01-21T00:00:00Z","publisher":"Springer","quality_controlled":"1","volume":10692,"department":[{"_id":"UlWa"}],"page":"160 - 166"},{"date_published":"2017-07-14T00:00:00Z","publisher":"International Press","volume":24,"quality_controlled":"1","department":[{"_id":"UlWa"}],"page":"1-44","ddc":["500"],"abstract":[{"lang":"eng","text":"A d-dimensional simplex S is called a k-reptile (or a k-reptile simplex) if it can be tiled by k simplices with disjoint interiors that are all mutually congruent and similar to S. For d = 2, triangular k-reptiles exist for all k of the form a^2, 3a^2 or a^2+b^2 and they have been completely characterized by Snover, Waiveris, and Williams. On the other hand, the only k-reptile simplices that are known for d ≥ 3, have k = m^d, where m is a positive integer. We substantially simplify the proof by Matoušek and the second author that for d = 3, k-reptile tetrahedra can exist only for k = m^3. We then prove a weaker analogue of this result for d = 4 by showing that four-dimensional k-reptile simplices can exist only for k = m^2."}],"publication_status":"published","_id":"701","file_date_updated":"2020-07-14T12:47:47Z","year":"2017","date_created":"2018-12-11T11:48:00Z","citation":{"apa":"Kynčl, J., &#38; Patakova, Z. (2017). On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4. <i>The Electronic Journal of Combinatorics</i>. International Press.","ista":"Kynčl J, Patakova Z. 2017. On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4. The Electronic Journal of Combinatorics. 24(3), 1–44.","mla":"Kynčl, Jan, and Zuzana Patakova. “On the Nonexistence of k Reptile Simplices in ℝ^3 and ℝ^4.” <i>The Electronic Journal of Combinatorics</i>, vol. 24, no. 3, International Press, 2017, pp. 1–44.","chicago":"Kynčl, Jan, and Zuzana Patakova. “On the Nonexistence of k Reptile Simplices in ℝ^3 and ℝ^4.” <i>The Electronic Journal of Combinatorics</i>. International Press, 2017.","short":"J. Kynčl, Z. Patakova, The Electronic Journal of Combinatorics 24 (2017) 1–44.","ieee":"J. Kynčl and Z. Patakova, “On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4,” <i>The Electronic Journal of Combinatorics</i>, vol. 24, no. 3. International Press, pp. 1–44, 2017.","ama":"Kynčl J, Patakova Z. On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4. <i>The Electronic Journal of Combinatorics</i>. 2017;24(3):1-44."},"publist_id":"6996","type":"journal_article","status":"public","month":"07","publication_identifier":{"issn":["10778926"]},"file":[{"date_created":"2018-12-12T10:14:25Z","date_updated":"2020-07-14T12:47:47Z","file_id":"5077","file_name":"IST-2018-984-v1+1_Patakova_on_the_nonexistence_of_k-reptile_simplices_in_R_3_and_R_4_2017.pdf","checksum":"a431e573e31df13bc0f66de3061006ec","access_level":"open_access","content_type":"application/pdf","relation":"main_file","file_size":544042,"creator":"system"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"14","oa_version":"Submitted Version","author":[{"last_name":"Kynčl","first_name":"Jan","full_name":"Kynčl, Jan"},{"last_name":"Patakova","id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683","first_name":"Zuzana","full_name":"Patakova, Zuzana"}],"publication":"The Electronic Journal of Combinatorics","language":[{"iso":"eng"}],"intvolume":"        24","has_accepted_license":"1","issue":"3","pubrep_id":"984","date_updated":"2021-01-12T08:11:28Z","oa":1,"title":"On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4"}]