[{"author":[{"id":"3AA52972-F248-11E8-B48F-1D18A9856A87","first_name":"Stephan Y","full_name":"Zhechev, Stephan Y","last_name":"Zhechev"}],"related_material":{"record":[{"id":"6774","status":"public","relation":"part_of_dissertation"}]},"day":"08","publisher":"Institute of Science and Technology Austria","citation":{"ieee":"S. Y. Zhechev, “Algorithmic aspects of homotopy theory and embeddability,” Institute of Science and Technology Austria, 2019.","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.","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>.","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.","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>"},"file":[{"creator":"szhechev","checksum":"3231e7cbfca3b5687366f84f0a57a0c0","file_size":1464227,"relation":"main_file","access_level":"open_access","file_name":"Stephan_Zhechev_thesis.pdf","date_created":"2019-08-07T13:02:50Z","date_updated":"2020-07-14T12:47:37Z","file_id":"6771","content_type":"application/pdf"},{"checksum":"85d65eb27b4377a9e332ee37a70f08b6","creator":"szhechev","content_type":"application/octet-stream","date_created":"2019-08-07T13:03:22Z","date_updated":"2020-07-14T12:47:37Z","file_id":"6772","file_name":"Stephan_Zhechev_thesis.tex","relation":"source_file","file_size":303988,"access_level":"closed"},{"checksum":"86b374d264ca2dd53e712728e253ee75","creator":"szhechev","date_created":"2019-08-07T13:03:34Z","file_id":"6773","date_updated":"2020-07-14T12:47:37Z","content_type":"application/zip","relation":"supplementary_material","file_size":1087004,"access_level":"closed","file_name":"supplementary_material.zip"}],"alternative_title":["ISTA Thesis"],"publication_status":"published","page":"104","month":"08","oa_version":"Published Version","status":"public","ddc":["514"],"degree_awarded":"PhD","OA_place":"publisher","doi":"10.15479/AT:ISTA:6681","supervisor":[{"last_name":"Wagner","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","orcid":"0000-0002-1494-0568"}],"department":[{"_id":"UlWa"}],"oa":1,"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","corr_author":"1","publication_identifier":{"issn":["2663-337X"]},"year":"2019","date_updated":"2026-04-16T12:20:40Z","date_created":"2019-07-26T11:14:34Z","abstract":[{"lang":"eng","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."}],"type":"dissertation","_id":"6681","has_accepted_license":"1","file_date_updated":"2020-07-14T12:47:37Z","language":[{"iso":"eng"}],"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"article_processing_charge":"No","title":"Algorithmic aspects of homotopy theory and embeddability","date_published":"2019-08-08T00:00:00Z"},{"oa_version":"Preprint","month":"10","article_type":"original","issue":"4","article_number":"50","status":"public","main_file_link":[{"url":"https://arxiv.org/abs/1709.09209","open_access":"1"}],"quality_controlled":"1","doi":"10.1145/3344549","day":"01","related_material":{"record":[{"id":"309","status":"public","relation":"earlier_version"}]},"author":[{"first_name":"Hugo","last_name":"Akitaya","full_name":"Akitaya, Hugo"},{"last_name":"Fulek","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Tóth, Csaba","last_name":"Tóth","first_name":"Csaba"}],"volume":15,"publisher":"ACM","project":[{"name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","call_identifier":"FWF"}],"publication_status":"published","citation":{"apa":"Akitaya, H., Fulek, R., &#38; Tóth, C. (2019). Recognizing weak embeddings of graphs. <i>ACM Transactions on Algorithms</i>. ACM. <a href=\"https://doi.org/10.1145/3344549\">https://doi.org/10.1145/3344549</a>","short":"H. Akitaya, R. Fulek, C. Tóth, ACM Transactions on Algorithms 15 (2019).","mla":"Akitaya, Hugo, et al. “Recognizing Weak Embeddings of Graphs.” <i>ACM Transactions on Algorithms</i>, vol. 15, no. 4, 50, ACM, 2019, doi:<a href=\"https://doi.org/10.1145/3344549\">10.1145/3344549</a>.","ista":"Akitaya H, Fulek R, Tóth C. 2019. Recognizing weak embeddings of graphs. ACM Transactions on Algorithms. 15(4), 50.","ama":"Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. <i>ACM Transactions on Algorithms</i>. 2019;15(4). doi:<a href=\"https://doi.org/10.1145/3344549\">10.1145/3344549</a>","chicago":"Akitaya, Hugo, Radoslav Fulek, and Csaba Tóth. “Recognizing Weak Embeddings of Graphs.” <i>ACM Transactions on Algorithms</i>. ACM, 2019. <a href=\"https://doi.org/10.1145/3344549\">https://doi.org/10.1145/3344549</a>.","ieee":"H. Akitaya, R. Fulek, and C. Tóth, “Recognizing weak embeddings of graphs,” <i>ACM Transactions on Algorithms</i>, vol. 15, no. 4. ACM, 2019."},"scopus_import":1,"intvolume":"        15","_id":"6982","type":"journal_article","language":[{"iso":"eng"}],"date_published":"2019-10-01T00:00:00Z","title":"Recognizing weak embeddings of graphs","department":[{"_id":"UlWa"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"date_created":"2019-11-04T15:45:17Z","publication":"ACM Transactions on Algorithms","year":"2019","date_updated":"2025-04-14T13:52:37Z","arxiv":1,"external_id":{"arxiv":["1709.09209"]},"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 2-manifold 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 the same point or overlapping arcs 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 ‖ ϕ − ψ ϵ ‖ < ϵ for every ϵ > 0, where ‖.‖ is the unform norm.\r\nA polynomial-time algorithm for recognizing weak embeddings has recently been found by Fulek and Kynčl. It reduces the problem to solving a system of linear equations over Z2. It runs in O(n2ω)≤ O(n4.75) time, where ω ∈ [2,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: We perform a sequence of local operations that gradually “untangles” the image ϕ(G) into an embedding ψ(G) or reports that ϕ is not a weak embedding. It combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations.\r\n"}]},{"author":[{"full_name":"Fulek, Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav"},{"full_name":"Kynčl, Jan","last_name":"Kynčl","first_name":"Jan"}],"day":"29","project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"},{"name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"publisher":"Springer Nature","volume":39,"citation":{"ieee":"R. Fulek and J. Kynčl, “Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4,” <i>Combinatorica</i>, vol. 39, no. 6. Springer Nature, pp. 1267–1279, 2019.","mla":"Fulek, Radoslav, and Jan Kynčl. “Counterexample to an Extension of the Hanani-Tutte Theorem on the Surface of Genus 4.” <i>Combinatorica</i>, vol. 39, no. 6, Springer Nature, 2019, pp. 1267–79, doi:<a href=\"https://doi.org/10.1007/s00493-019-3905-7\">10.1007/s00493-019-3905-7</a>.","ama":"Fulek R, Kynčl J. Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4. <i>Combinatorica</i>. 2019;39(6):1267-1279. doi:<a href=\"https://doi.org/10.1007/s00493-019-3905-7\">10.1007/s00493-019-3905-7</a>","chicago":"Fulek, Radoslav, and Jan Kynčl. “Counterexample to an Extension of the Hanani-Tutte Theorem on the Surface of Genus 4.” <i>Combinatorica</i>. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/s00493-019-3905-7\">https://doi.org/10.1007/s00493-019-3905-7</a>.","ista":"Fulek R, Kynčl J. 2019. Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4. Combinatorica. 39(6), 1267–1279.","short":"R. Fulek, J. Kynčl, Combinatorica 39 (2019) 1267–1279.","apa":"Fulek, R., &#38; Kynčl, J. (2019). Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4. <i>Combinatorica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00493-019-3905-7\">https://doi.org/10.1007/s00493-019-3905-7</a>"},"isi":1,"publication_status":"published","page":"1267-1279","ec_funded":1,"scopus_import":"1","month":"10","article_type":"original","oa_version":"Preprint","status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1709.00508"}],"issue":"6","quality_controlled":"1","doi":"10.1007/s00493-019-3905-7","department":[{"_id":"UlWa"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","oa":1,"publication_identifier":{"eissn":["1439-6912"],"issn":["0209-9683"]},"arxiv":1,"date_created":"2019-11-18T14:29:50Z","publication":"Combinatorica","year":"2019","date_updated":"2025-04-14T13:52:37Z","abstract":[{"lang":"eng","text":"We find a graph of genus 5 and its drawing on the orientable surface of genus 4 with every pair of independent edges crossing an even number of times. This shows that the strong Hanani–Tutte theorem cannot be extended to the orientable surface of genus 4. As a base step in the construction we use a counterexample to an extension of the unified Hanani–Tutte theorem on the torus."}],"external_id":{"isi":["000493267200003"],"arxiv":["1709.00508"]},"intvolume":"        39","type":"journal_article","_id":"7034","language":[{"iso":"eng"}],"article_processing_charge":"No","title":"Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4","date_published":"2019-10-29T00:00:00Z"},{"date_updated":"2026-04-08T07:21:27Z","year":"2019","publication":"Journal of Computational Geometry","date_created":"2019-11-23T12:14:09Z","arxiv":1,"publication_identifier":{"issn":["1920-180X"]},"external_id":{"arxiv":["1712.00434"]},"abstract":[{"text":"In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how \"simple\" or \"thin\" 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.\r\nIn 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).\r\nWe derive these results from work of Agol, of Scharlemann and Thompson, and of Scharlemann, Schultens and Saito 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 18(k+1) (resp. 4(3k+1)).","lang":"eng"}],"department":[{"_id":"UlWa"}],"oa":1,"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:47:49Z","date_published":"2019-11-01T00:00:00Z","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"article_processing_charge":"No","title":"On the treewidth of triangulated 3-manifolds","intvolume":"        10","has_accepted_license":"1","_id":"7093","type":"journal_article","page":"70–98","publication_status":"published","file":[{"creator":"khuszar","checksum":"c872d590d38d538404782bca20c4c3f5","file_size":857590,"access_level":"open_access","relation":"main_file","file_name":"479-1917-1-PB.pdf","date_updated":"2020-07-14T12:47:49Z","file_id":"7094","date_created":"2019-11-23T12:35:16Z","content_type":"application/pdf"}],"citation":{"ieee":"K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,” <i>Journal of Computational Geometry</i>, vol. 10, no. 2. Computational Geometry Laborartoy, pp. 70–98, 2019.","ama":"Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds. <i>Journal of Computational Geometry</i>. 2019;10(2):70–98. doi:<a href=\"https://doi.org/10.20382/JOGC.V10I2A5\">10.20382/JOGC.V10I2A5</a>","ista":"Huszár K, Spreer J, Wagner U. 2019. On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. 10(2), 70–98.","mla":"Huszár, Kristóf, et al. “On the Treewidth of Triangulated 3-Manifolds.” <i>Journal of Computational Geometry</i>, vol. 10, no. 2, Computational Geometry Laborartoy, 2019, pp. 70–98, doi:<a href=\"https://doi.org/10.20382/JOGC.V10I2A5\">10.20382/JOGC.V10I2A5</a>.","chicago":"Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds.” <i>Journal of Computational Geometry</i>. Computational Geometry Laborartoy, 2019. <a href=\"https://doi.org/10.20382/JOGC.V10I2A5\">https://doi.org/10.20382/JOGC.V10I2A5</a>.","short":"K. Huszár, J. Spreer, U. Wagner, Journal of Computational Geometry 10 (2019) 70–98.","apa":"Huszár, K., Spreer, J., &#38; Wagner, U. (2019). On the treewidth of triangulated 3-manifolds. <i>Journal of Computational Geometry</i>. Computational Geometry Laborartoy. <a href=\"https://doi.org/10.20382/JOGC.V10I2A5\">https://doi.org/10.20382/JOGC.V10I2A5</a>"},"scopus_import":"1","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"285"},{"id":"8032","status":"public","relation":"part_of_dissertation"}]},"day":"01","author":[{"orcid":"0000-0002-5445-5057","first_name":"Kristóf","id":"33C26278-F248-11E8-B48F-1D18A9856A87","full_name":"Huszár, Kristóf","last_name":"Huszár"},{"first_name":"Jonathan","full_name":"Spreer, Jonathan","last_name":"Spreer"},{"full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"volume":10,"publisher":"Computational Geometry Laborartoy","doi":"10.20382/JOGC.V10I2A5","quality_controlled":"1","oa_version":"Published Version","article_type":"original","month":"11","issue":"2","ddc":["514"],"status":"public"},{"department":[{"_id":"UlWa"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-06-04T07:49:03Z","year":"2019","publication":"Journal of the ACM","date_created":"2019-11-26T10:13:59Z","publication_identifier":{"issn":["0004-5411"]},"arxiv":1,"external_id":{"arxiv":["1711.08436"],"isi":["000495406300007"]},"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. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable."}],"intvolume":"        66","_id":"7108","type":"journal_article","language":[{"iso":"eng"}],"date_published":"2019-06-01T00:00:00Z","article_processing_charge":"No","title":"Shellability is NP-complete","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"184"}]},"day":"01","author":[{"first_name":"Xavier","last_name":"Goaoc","full_name":"Goaoc, Xavier"},{"last_name":"Patak","full_name":"Patak, Pavel","first_name":"Pavel","id":"B593B804-1035-11EA-B4F1-947645A5BB83"},{"orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","last_name":"Patakova","full_name":"Patakova, Zuzana"},{"full_name":"Tancer, Martin","last_name":"Tancer","first_name":"Martin"},{"first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","last_name":"Wagner"}],"volume":66,"publisher":"ACM","publication_status":"published","isi":1,"citation":{"short":"X. Goaoc, P. Patak, Z. Patakova, M. Tancer, U. Wagner, Journal of the ACM 66 (2019).","apa":"Goaoc, X., Patak, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2019). Shellability is NP-complete. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/3314024\">https://doi.org/10.1145/3314024</a>","ama":"Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete. <i>Journal of the ACM</i>. 2019;66(3). doi:<a href=\"https://doi.org/10.1145/3314024\">10.1145/3314024</a>","ista":"Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. 2019. Shellability is NP-complete. Journal of the ACM. 66(3), 21.","chicago":"Goaoc, Xavier, Pavel Patak, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Shellability Is NP-Complete.” <i>Journal of the ACM</i>. ACM, 2019. <a href=\"https://doi.org/10.1145/3314024\">https://doi.org/10.1145/3314024</a>.","mla":"Goaoc, Xavier, et al. “Shellability Is NP-Complete.” <i>Journal of the ACM</i>, vol. 66, no. 3, 21, ACM, 2019, doi:<a href=\"https://doi.org/10.1145/3314024\">10.1145/3314024</a>.","ieee":"X. Goaoc, P. Patak, Z. Patakova, M. Tancer, and U. Wagner, “Shellability is NP-complete,” <i>Journal of the ACM</i>, vol. 66, no. 3. ACM, 2019."},"scopus_import":"1","oa_version":"Preprint","article_type":"original","month":"06","article_number":"21","issue":"3","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1711.08436"}],"status":"public","doi":"10.1145/3314024","quality_controlled":"1"},{"main_file_link":[{"url":"https://arxiv.org/abs/1908.08129","open_access":"1"}],"status":"public","month":"11","conference":{"start_date":"2019-09-17","name":"GD: Graph Drawing and Network Visualization","end_date":"2019-09-20","location":"Prague, Czech Republic"},"oa_version":"Preprint","doi":"10.1007/978-3-030-35802-0_18","quality_controlled":"1","project":[{"grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"}],"publisher":"Springer Nature","volume":11904,"author":[{"last_name":"Arroyo Guevara","full_name":"Arroyo Guevara, Alan M","orcid":"0000-0003-2401-8670","first_name":"Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Derka, Martin","last_name":"Derka","first_name":"Martin"},{"first_name":"Irene","full_name":"Parada, Irene","last_name":"Parada"}],"day":"28","ec_funded":1,"scopus_import":"1","isi":1,"citation":{"chicago":"Arroyo Guevara, Alan M, Martin Derka, and Irene Parada. “Extending Simple Drawings.” In <i>27th International Symposium on Graph Drawing and Network Visualization</i>, 11904:230–43. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-35802-0_18\">https://doi.org/10.1007/978-3-030-35802-0_18</a>.","ama":"Arroyo Guevara AM, Derka M, Parada I. Extending simple drawings. In: <i>27th International Symposium on Graph Drawing and Network Visualization</i>. Vol 11904. Springer Nature; 2019:230-243. doi:<a href=\"https://doi.org/10.1007/978-3-030-35802-0_18\">10.1007/978-3-030-35802-0_18</a>","mla":"Arroyo Guevara, Alan M., et al. “Extending Simple Drawings.” <i>27th International Symposium on Graph Drawing and Network Visualization</i>, vol. 11904, Springer Nature, 2019, pp. 230–43, doi:<a href=\"https://doi.org/10.1007/978-3-030-35802-0_18\">10.1007/978-3-030-35802-0_18</a>.","ista":"Arroyo Guevara AM, Derka M, Parada I. 2019. Extending simple drawings. 27th International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LNCS, vol. 11904, 230–243.","short":"A.M. Arroyo Guevara, M. Derka, I. Parada, in:, 27th International Symposium on Graph Drawing and Network Visualization, Springer Nature, 2019, pp. 230–243.","apa":"Arroyo Guevara, A. M., Derka, M., &#38; Parada, I. (2019). Extending simple drawings. In <i>27th International Symposium on Graph Drawing and Network Visualization</i> (Vol. 11904, pp. 230–243). Prague, Czech Republic: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-35802-0_18\">https://doi.org/10.1007/978-3-030-35802-0_18</a>","ieee":"A. M. Arroyo Guevara, M. Derka, and I. Parada, “Extending simple drawings,” in <i>27th International Symposium on Graph Drawing and Network Visualization</i>, Prague, Czech Republic, 2019, vol. 11904, pp. 230–243."},"alternative_title":["LNCS"],"publication_status":"published","page":"230-243","type":"conference","_id":"7230","intvolume":"     11904","article_processing_charge":"No","title":"Extending simple drawings","date_published":"2019-11-28T00:00:00Z","language":[{"iso":"eng"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa":1,"department":[{"_id":"UlWa"}],"abstract":[{"text":"Simple drawings of graphs are those in which each pair of edges share at most one point, either a common endpoint or a proper crossing. In this paper we study the problem of extending a simple drawing D(G) of a graph G by inserting a set of edges from the complement of G into D(G) such that the result is a simple drawing. In the context of rectilinear drawings, the problem is trivial. For pseudolinear drawings, the existence of such an extension follows from Levi’s enlargement lemma. In contrast, we prove that deciding if a given set of edges can be inserted into a simple drawing is NP-complete. Moreover, we show that the maximization version of the problem is APX-hard. We also present a polynomial-time algorithm for deciding whether one edge uv can be inserted into D(G) when {u,v} is a dominating set for the graph G.","lang":"eng"}],"external_id":{"isi":["000612918800018"],"arxiv":["1908.08129"]},"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["978-3-0303-5801-3"]},"arxiv":1,"date_created":"2020-01-05T23:00:47Z","publication":"27th International Symposium on Graph Drawing and Network Visualization","year":"2019","date_updated":"2025-04-14T07:44:07Z"},{"status":"public","ddc":["000"],"article_number":"39","month":"06","oa_version":"Published Version","conference":{"end_date":"2019-06-21","name":"SoCG: Symposium on Computational Geometry","start_date":"2019-06-18","location":"Portland, OR, United States"},"quality_controlled":"1","doi":"10.4230/LIPICS.SOCG.2019.39","project":[{"_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":129,"author":[{"full_name":"Fulek, Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kyncl","full_name":"Kyncl, Jan","first_name":"Jan"}],"day":"01","scopus_import":1,"file":[{"file_size":628347,"relation":"main_file","access_level":"open_access","file_name":"2019_LIPIcs_Fulek.pdf","date_created":"2020-02-04T09:14:31Z","file_id":"7445","date_updated":"2020-07-14T12:47:57Z","content_type":"application/pdf","creator":"dernst","checksum":"aac37b09118cc0ab58cf77129e691f8c"}],"citation":{"ieee":"R. Fulek and J. Kyncl, “Z_2-Genus of graphs and minimum rank of partial symmetric matrices,” in <i>35th International Symposium on Computational Geometry (SoCG 2019)</i>, Portland, OR, United States, 2019, vol. 129.","chicago":"Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices.” In <i>35th International Symposium on Computational Geometry (SoCG 2019)</i>, Vol. 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.39\">https://doi.org/10.4230/LIPICS.SOCG.2019.39</a>.","ista":"Fulek R, Kyncl J. 2019. Z_2-Genus of graphs and minimum rank of partial symmetric matrices. 35th International Symposium on Computational Geometry (SoCG 2019). SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 39.","mla":"Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices.” <i>35th International Symposium on Computational Geometry (SoCG 2019)</i>, vol. 129, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.39\">10.4230/LIPICS.SOCG.2019.39</a>.","ama":"Fulek R, Kyncl J. Z_2-Genus of graphs and minimum rank of partial symmetric matrices. In: <i>35th International Symposium on Computational Geometry (SoCG 2019)</i>. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.39\">10.4230/LIPICS.SOCG.2019.39</a>","short":"R. Fulek, J. Kyncl, in:, 35th International Symposium on Computational Geometry (SoCG 2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.","apa":"Fulek, R., &#38; Kyncl, J. (2019). Z_2-Genus of graphs and minimum rank of partial symmetric matrices. In <i>35th International Symposium on Computational Geometry (SoCG 2019)</i> (Vol. 129). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.39\">https://doi.org/10.4230/LIPICS.SOCG.2019.39</a>"},"publication_status":"published","alternative_title":["LIPIcs"],"type":"conference","_id":"7401","has_accepted_license":"1","intvolume":"       129","title":"Z_2-Genus of graphs and minimum rank of partial symmetric matrices","article_processing_charge":"No","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_published":"2019-06-01T00:00:00Z","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:47:57Z","corr_author":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"department":[{"_id":"UlWa"}],"abstract":[{"lang":"eng","text":"The genus g(G) of a graph G is the minimum g such that G has an embedding on the orientable surface M_g of genus g. 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 Z_2-genus of a graph G, denoted by g_0(G), is the minimum g such that G has an independently even drawing on M_g. By a result of Battle, Harary, Kodama and Youngs from 1962, the graph genus is additive over 2-connected blocks. In 2013, Schaefer and Stefankovic proved that the Z_2-genus of a graph is additive over 2-connected blocks as well, and asked whether this result can be extended to so-called 2-amalgamations, as an analogue of results by Decker, Glover, Huneke, and Stahl for the genus. We give the following partial answer. If G=G_1 cup G_2, G_1 and G_2 intersect in two vertices u and v, and G-u-v has k connected components (among which we count the edge uv if present), then |g_0(G)-(g_0(G_1)+g_0(G_2))|<=k+1. For complete bipartite graphs K_{m,n}, with n >= m >= 3, we prove that g_0(K_{m,n})/g(K_{m,n})=1-O(1/n). Similar results are proved also for the Euler Z_2-genus. We express the Z_2-genus of a graph using the minimum rank of partial symmetric matrices over Z_2; a problem that might be of independent interest. "}],"external_id":{"arxiv":["1903.08637"]},"arxiv":1,"publication_identifier":{"isbn":["978-3-95977-104-7"],"issn":["1868-8969"]},"date_created":"2020-01-29T16:17:05Z","publication":"35th International Symposium on Computational Geometry (SoCG 2019)","year":"2019","date_updated":"2024-10-09T20:59:14Z"},{"date_updated":"2025-07-10T11:52:21Z","year":"2018","date_created":"2018-12-11T11:45:37Z","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).","arxiv":1,"publication_identifier":{"issn":["1868-8969"]},"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))."}],"department":[{"_id":"UlWa"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"7614","file_date_updated":"2020-07-14T12:45:51Z","language":[{"iso":"eng"}],"date_published":"2018-06-01T00:00:00Z","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"title":"On the treewidth of triangulated 3-manifolds","article_processing_charge":"No","intvolume":"        99","has_accepted_license":"1","type":"conference","_id":"285","alternative_title":["LIPIcs"],"publication_status":"published","citation":{"short":"K. Huszár, J. Spreer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","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>","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>","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>.","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>.","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.","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."},"file":[{"checksum":"530d084116778135d5bffaa317479cac","creator":"dernst","date_created":"2018-12-17T15:32:38Z","file_id":"5713","date_updated":"2020-07-14T12:45:51Z","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_size":642522,"file_name":"2018_LIPIcs_Huszar.pdf"}],"scopus_import":"1","related_material":{"record":[{"id":"7093","relation":"later_version","status":"public"}]},"day":"01","author":[{"last_name":"Huszár","full_name":"Huszár, Kristóf","first_name":"Kristóf","id":"33C26278-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5445-5057"},{"full_name":"Spreer, Jonathan","last_name":"Spreer","first_name":"Jonathan"},{"last_name":"Wagner","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli"}],"volume":99,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","doi":"10.4230/LIPIcs.SoCG.2018.46","quality_controlled":"1","conference":{"end_date":"2018-06-14","start_date":"2018-06-11","name":"SoCG: Symposium on Computational Geometry","location":"Budapest, Hungary"},"oa_version":"Submitted Version","month":"06","article_number":"46","ddc":["516","000"],"status":"public"},{"type":"conference","_id":"185","has_accepted_license":"1","intvolume":"        99","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"title":"Hanani-Tutte for approximating maps of graphs","date_published":"2018-01-01T00:00:00Z","file_date_updated":"2020-07-14T12:45:19Z","language":[{"iso":"eng"}],"publist_id":"7735","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"UlWa"}],"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."}],"publication_identifier":{"isbn":["978-3-95977-066-8"]},"date_updated":"2021-01-12T06:53:36Z","year":"2018","date_created":"2018-12-11T11:45:04Z","status":"public","article_number":"39","ddc":["510"],"month":"01","conference":{"location":"Budapest, Hungary","end_date":"2018-06-14","start_date":"2018-06-11","name":"SoCG: Symposium on Computational Geometry"},"oa_version":"Published Version","doi":"10.4230/LIPIcs.SoCG.2018.39","quality_controlled":"1","project":[{"name":"Eliminating intersections in drawings of graphs","grant_number":"M02281","call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":99,"author":[{"last_name":"Fulek","full_name":"Fulek, Radoslav","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774"},{"first_name":"Jan","full_name":"Kynčl, Jan","last_name":"Kynčl"}],"day":"01","scopus_import":1,"file":[{"creator":"dernst","checksum":"f1b94f1a75b37c414a1f61d59fb2cd4c","access_level":"open_access","relation":"main_file","file_size":718857,"file_name":"2018_LIPIcs_Fulek.pdf","date_created":"2018-12-17T12:33:52Z","file_id":"5701","date_updated":"2020-07-14T12:45:19Z","content_type":"application/pdf"}],"citation":{"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.","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>","short":"R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","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>.","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>","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.","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>."},"publication_status":"published","alternative_title":["Leibniz International Proceedings in Information, LIPIcs"]},{"day":"11","related_material":{"record":[{"id":"11593","status":"public","relation":"later_version"}]},"author":[{"orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav","full_name":"Fulek, Radoslav","last_name":"Fulek"},{"first_name":"Jan","last_name":"Kynčl","full_name":"Kynčl, Jan"}],"volume":99,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","call_identifier":"FWF"}],"page":"40.1 - 40.14","alternative_title":["LIPIcs"],"publication_status":"published","citation":{"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>.","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.","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>","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>.","short":"R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 40.1-40.14.","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>","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."},"scopus_import":"1","conference":{"location":"Budapest, Hungary","end_date":"2018-06-14","start_date":"2018-06-11","name":"SoCG: Symposium on Computational Geometry"},"oa_version":"Submitted Version","month":"06","status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1803.05085"}],"quality_controlled":"1","doi":"10.4230/LIPIcs.SoCG.2018.40","department":[{"_id":"UlWa"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"publist_id":"7734","date_created":"2018-12-11T11:45:05Z","date_updated":"2025-04-14T13:52:37Z","year":"2018","arxiv":1,"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"}],"intvolume":"        99","type":"conference","_id":"186","language":[{"iso":"eng"}],"date_published":"2018-06-11T00:00:00Z","article_processing_charge":"No","title":"The ℤ2-Genus of Kuratowski minors"},{"isi":1,"citation":{"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>","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>.","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>.","ista":"Fulek R, Tóth CD. 2018. Crossing minimization in perturbed drawings. GD: 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 GD: 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>","short":"R. Fulek, C.D. Tóth, in:, Springer, 2018, pp. 229–241.","ieee":"R. Fulek and C. D. Tóth, “Crossing minimization in perturbed drawings,” presented at the GD: Graph Drawing and Network Visualization, Barcelona, Spain, 2018, vol. 11282, pp. 229–241."},"alternative_title":["LNCS"],"page":"229-241","publication_status":"published","scopus_import":"1","author":[{"orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav","last_name":"Fulek","full_name":"Fulek, Radoslav"},{"first_name":"Csaba D.","full_name":"Tóth, Csaba D.","last_name":"Tóth"}],"day":"18","publisher":"Springer","volume":"11282 ","quality_controlled":"1","doi":"10.1007/978-3-030-04414-5_16","month":"12","conference":{"location":"Barcelona, Spain","start_date":"2018-09-26","name":"GD: Graph Drawing and Network Visualization","end_date":"2018-09-28"},"oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1808.07608"}],"status":"public","publication_identifier":{"isbn":["9783030044138"]},"arxiv":1,"date_created":"2018-12-30T22:59:15Z","date_updated":"2025-07-10T11:53:00Z","year":"2018","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"}],"external_id":{"arxiv":["1808.07608"],"isi":["000672802500016"]},"department":[{"_id":"UlWa"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"language":[{"iso":"eng"}],"article_processing_charge":"No","title":"Crossing minimization in perturbed drawings","date_published":"2018-12-18T00:00:00Z","type":"conference","_id":"5791"},{"isi":1,"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>","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>.","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.","short":"S. Rohou, P. Franek, C. Aubry, L. Jaulin, The International Journal of Robotics Research 37 (2018) 1500–1516.","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>"},"publication_status":"published","page":"1500-1516","scopus_import":"1","author":[{"last_name":"Rohou","full_name":"Rohou, Simon","first_name":"Simon"},{"orcid":"0000-0001-8878-8397","id":"473294AE-F248-11E8-B48F-1D18A9856A87","first_name":"Peter","last_name":"Franek","full_name":"Franek, Peter"},{"last_name":"Aubry","full_name":"Aubry, Clément","first_name":"Clément"},{"first_name":"Luc","last_name":"Jaulin","full_name":"Jaulin, Luc"}],"day":"24","publisher":"SAGE Publications","volume":37,"doi":"10.1177/0278364918808367","quality_controlled":"1","month":"10","oa_version":"Preprint","status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1712.01341"}],"issue":"12","publication_identifier":{"issn":["0278-3649"],"eissn":["1741-3176"]},"arxiv":1,"date_updated":"2023-09-19T10:41:59Z","year":"2018","date_created":"2019-02-13T09:36:20Z","publication":"The International Journal of Robotics Research","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."}],"external_id":{"isi":["000456881100004"],"arxiv":["1712.01341"]},"department":[{"_id":"UlWa"}],"oa":1,"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","language":[{"iso":"eng"}],"article_processing_charge":"No","title":"Proving the existence of loops in robot trajectories","date_published":"2018-10-24T00:00:00Z","intvolume":"        37","type":"journal_article","_id":"5960"},{"ec_funded":1,"citation":{"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.","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>.","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>","ista":"Akopyan A, Avvakumov S. 2018. Any cyclic quadrilateral can be inscribed in any closed convex smooth curve. Forum of Mathematics, Sigma. 6, e7.","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>.","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>","short":"A. Akopyan, S. Avvakumov, Forum of Mathematics, Sigma 6 (2018)."},"file":[{"creator":"dernst","checksum":"5a71b24ba712a3eb2e46165a38fbc30a","file_size":249246,"access_level":"open_access","relation":"main_file","file_name":"2018_ForumMahtematics_Akopyan.pdf","date_created":"2019-04-30T06:14:58Z","date_updated":"2020-07-14T12:47:28Z","file_id":"6356","content_type":"application/pdf"}],"isi":1,"publication_status":"published","project":[{"name":"Optimal Transport and Stochastic Dynamics","_id":"256E75B8-B435-11E9-9278-68D0E5697425","grant_number":"716117","call_identifier":"H2020"}],"publisher":"Cambridge University Press","volume":6,"author":[{"last_name":"Akopyan","full_name":"Akopyan, Arseniy","id":"430D2C90-F248-11E8-B48F-1D18A9856A87","first_name":"Arseniy","orcid":"0000-0002-2548-617X"},{"orcid":"0000-0002-7840-5062","first_name":"Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","full_name":"Avvakumov, Sergey","last_name":"Avvakumov"}],"day":"31","related_material":{"record":[{"id":"8156","relation":"dissertation_contains","status":"public"}]},"doi":"10.1017/fms.2018.7","quality_controlled":"1","status":"public","ddc":["510"],"article_number":"e7","month":"05","oa_version":"Published Version","abstract":[{"lang":"eng","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."}],"external_id":{"arxiv":["1712.10205"],"isi":["000433915500001"]},"publication_identifier":{"issn":["2050-5094"]},"arxiv":1,"date_created":"2019-04-30T06:09:57Z","publication":"Forum of Mathematics, Sigma","date_updated":"2026-04-08T07:25:54Z","year":"2018","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","corr_author":"1","oa":1,"department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"JaMa"}],"article_processing_charge":"No","title":"Any cyclic quadrilateral can be inscribed in any closed convex smooth curve","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_published":"2018-05-31T00:00:00Z","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:47:28Z","_id":"6355","type":"journal_article","has_accepted_license":"1","intvolume":"         6"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"publist_id":"7736","department":[{"_id":"UlWa"}],"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."}],"date_created":"2018-12-11T11:45:04Z","year":"2018","date_updated":"2025-06-04T07:49:02Z","acknowledgement":"Partially supported by the project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM) of Czech-French collaboration.","has_accepted_license":"1","_id":"184","type":"conference","intvolume":"        99","date_published":"2018-06-11T00:00:00Z","title":"Shellability is NP-complete","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"file_date_updated":"2020-07-14T12:45:18Z","language":[{"iso":"eng"}],"volume":99,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","day":"11","related_material":{"record":[{"relation":"later_version","status":"public","id":"7108"}]},"author":[{"first_name":"Xavier","last_name":"Goaoc","full_name":"Goaoc, Xavier"},{"first_name":"Pavel","full_name":"Paták, Pavel","last_name":"Paták"},{"id":"48B57058-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","orcid":"0000-0002-3975-1683","full_name":"Patakova, Zuzana","last_name":"Patakova"},{"last_name":"Tancer","full_name":"Tancer, Martin","orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","first_name":"Martin"},{"last_name":"Wagner","full_name":"Wagner, Uli","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"scopus_import":1,"publication_status":"published","page":"41:1 - 41:16","alternative_title":["Leibniz International Proceedings in Information, LIPIcs"],"citation":{"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>","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>","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>.","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>.","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."},"file":[{"file_name":"2018_LIPIcs_Goaoc.pdf","relation":"main_file","access_level":"open_access","file_size":718414,"content_type":"application/pdf","file_id":"5725","date_updated":"2020-07-14T12:45:18Z","date_created":"2018-12-17T16:35:02Z","creator":"dernst","checksum":"d12bdd60f04a57307867704b5f930afd"}],"ddc":["516","000"],"status":"public","conference":{"end_date":"2018-06-14","name":"SoCG: Symposium on Computational Geometry","start_date":"2018-06-11","location":"Budapest, Hungary"},"oa_version":"Published Version","month":"06","doi":"10.4230/LIPIcs.SoCG.2018.41","quality_controlled":"1"},{"doi":"10.1137/1.9781611975031.20","quality_controlled":"1","month":"01","conference":{"location":"New Orleans, LA, USA","end_date":"2018-01-10","start_date":"2018-01-07","name":"SODA: Symposium on Discrete Algorithms"},"oa_version":"Preprint","status":"public","main_file_link":[{"url":"https://arxiv.org/abs/1709.09209","open_access":"1"}],"isi":1,"citation":{"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>","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.","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>.","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>","short":"H. Akitaya, R. Fulek, C. Tóth, in:, ACM, 2018, pp. 274–292.","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."},"publication_status":"published","page":"274 - 292","scopus_import":"1","author":[{"last_name":"Akitaya","full_name":"Akitaya, Hugo","first_name":"Hugo"},{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek"},{"first_name":"Csaba","full_name":"Tóth, Csaba","last_name":"Tóth"}],"day":"01","related_material":{"record":[{"id":"6982","relation":"later_version","status":"public"}]},"publisher":"ACM","project":[{"name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","call_identifier":"FWF"}],"language":[{"iso":"eng"}],"title":"Recognizing weak embeddings of graphs","article_processing_charge":"No","date_published":"2018-01-01T00:00:00Z","type":"conference","_id":"309","arxiv":1,"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.","date_created":"2018-12-11T11:45:45Z","year":"2018","date_updated":"2025-04-14T13:52:37Z","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":{"arxiv":["1709.09209"],"isi":["000483921200021"]},"department":[{"_id":"UlWa"}],"publist_id":"7556","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa":1},{"language":[{"iso":"eng"}],"article_processing_charge":"No","title":"Embeddability in the 3-Sphere is decidable","date_published":"2018-01-01T00:00:00Z","intvolume":"        65","type":"journal_article","_id":"425","arxiv":1,"date_updated":"2025-06-11T07:59:02Z","year":"2018","publication":"Journal of the ACM","date_created":"2018-12-11T11:46:24Z","abstract":[{"lang":"eng","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."}],"external_id":{"isi":["000425685900006"],"arxiv":["1402.0815"]},"department":[{"_id":"UlWa"}],"publist_id":"7398","oa":1,"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","doi":"10.1145/3078632","quality_controlled":"1","article_type":"original","month":"01","oa_version":"Preprint","main_file_link":[{"url":"https://arxiv.org/abs/1402.0815","open_access":"1"}],"status":"public","article_number":"5","issue":"1","citation":{"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.","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>.","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>","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>","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Journal of the ACM 65 (2018).","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."},"isi":1,"publication_status":"published","ec_funded":1,"scopus_import":"1","author":[{"last_name":"Matoušek","full_name":"Matoušek, Jiří","first_name":"Jiří"},{"full_name":"Sedgwick, Eric","last_name":"Sedgwick","first_name":"Eric"},{"orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","full_name":"Tancer, Martin","last_name":"Tancer"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","full_name":"Wagner, Uli"}],"related_material":{"record":[{"id":"2157","relation":"earlier_version","status":"public"}]},"day":"01","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"}],"publisher":"ACM","volume":65},{"author":[{"full_name":"Fulek, Radoslav","last_name":"Fulek","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774"},{"first_name":"János","last_name":"Pach","full_name":"Pach, János"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"5857"}]},"day":"21","publisher":"Springer","volume":10692,"citation":{"ieee":"R. Fulek and J. Pach, “Thrackles: An improved upper bound,” presented at the GD: Graph Drawing and Network Visualization, Boston, MA, United States, 2018, vol. 10692, pp. 160–166.","apa":"Fulek, R., &#38; Pach, J. (2018). Thrackles: An improved upper bound (Vol. 10692, pp. 160–166). Presented at the GD: 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>","short":"R. Fulek, J. Pach, in:, Springer, 2018, pp. 160–166.","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>.","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>","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>.","ista":"Fulek R, Pach J. 2018. Thrackles: An improved upper bound. GD: Graph Drawing and Network Visualization, LNCS, vol. 10692, 160–166."},"page":"160 - 166","alternative_title":["LNCS"],"publication_status":"published","scopus_import":"1","month":"01","oa_version":"Submitted Version","conference":{"end_date":"2017-09-27","start_date":"201-09-25","name":"GD: Graph Drawing and Network Visualization","location":"Boston, MA, United States"},"main_file_link":[{"url":"https://arxiv.org/abs/1708.08037","open_access":"1"}],"status":"public","quality_controlled":"1","doi":"10.1007/978-3-319-73915-1_14","department":[{"_id":"UlWa"}],"publist_id":"7390","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","arxiv":1,"year":"2018","date_updated":"2026-04-16T09:48:11Z","date_created":"2018-12-11T11:46:27Z","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"]},"intvolume":"     10692","_id":"433","type":"conference","language":[{"iso":"eng"}],"article_processing_charge":"No","title":"Thrackles: An improved upper bound","date_published":"2018-01-21T00:00:00Z"},{"page":"177-231","publication_status":"published","citation":{"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>","short":"M. Filakovský, P. Franek, U. Wagner, S.Y. Zhechev, Journal of Applied and Computational Topology 2 (2018) 177–231.","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.","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>.","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>","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>.","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."},"file":[{"creator":"dernst","checksum":"cf9e7fcd2a113dd4828774fc75cdb7e8","file_name":"2018_JourAppliedComputTopology_Filakovsky.pdf","file_size":1056278,"access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2019-08-08T06:55:21Z","date_updated":"2020-07-14T12:47:40Z","file_id":"6775"}],"scopus_import":"1","related_material":{"record":[{"id":"6681","status":"public","relation":"dissertation_contains"}]},"day":"01","author":[{"last_name":"Filakovský","full_name":"Filakovský, Marek","first_name":"Marek","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0001-8878-8397","id":"473294AE-F248-11E8-B48F-1D18A9856A87","first_name":"Peter","full_name":"Franek, Peter","last_name":"Franek"},{"orcid":"0000-0002-1494-0568","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","full_name":"Wagner, Uli"},{"full_name":"Zhechev, Stephan Y","last_name":"Zhechev","id":"3AA52972-F248-11E8-B48F-1D18A9856A87","first_name":"Stephan Y"}],"volume":2,"project":[{"call_identifier":"FWF","grant_number":"M01980","_id":"25F8B9BC-B435-11E9-9278-68D0E5697425","name":"Robust Invariants of Nonlinear Systems"},{"name":"FWF Open Access Fund","call_identifier":"FWF","_id":"3AC91DDA-15DF-11EA-824D-93A3E7B544D1"}],"publisher":"Springer","doi":"10.1007/s41468-018-0021-5","quality_controlled":"1","oa_version":"Published Version","article_type":"original","month":"12","ddc":["514"],"issue":"3-4","status":"public","year":"2018","date_updated":"2026-04-08T13:56:01Z","publication":"Journal of Applied and Computational Topology","date_created":"2019-08-08T06:47:40Z","publication_identifier":{"eissn":["2367-1734"],"issn":["2367-1726"]},"abstract":[{"lang":"eng","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(𝑋) ."}],"department":[{"_id":"UlWa"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:47:40Z","date_published":"2018-12-01T00:00:00Z","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"title":"Computing simplicial representatives of homotopy group elements","intvolume":"         2","has_accepted_license":"1","_id":"6774","type":"journal_article"},{"doi":"10.1007/s10711-017-0291-4","quality_controlled":"1","status":"public","ddc":["514","516"],"issue":"1","month":"08","oa_version":"Published Version","pubrep_id":"912","scopus_import":"1","file":[{"content_type":"application/pdf","date_updated":"2020-07-14T12:47:58Z","file_id":"5835","date_created":"2019-01-15T13:44:05Z","file_name":"s10711-017-0291-4.pdf","access_level":"open_access","file_size":412486,"relation":"main_file","checksum":"d2f70fc132156504aa4c626aa378a7ab","creator":"kschuh"}],"citation":{"short":"D. Dotterrer, T. Kaufman, U. Wagner, Geometriae Dedicata 195 (2018) 307–317.","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>","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>.","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>","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>.","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."},"isi":1,"page":"307–317","publication_status":"published","publisher":"Springer","project":[{"name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","_id":"25FA3206-B435-11E9-9278-68D0E5697425","grant_number":"PP00P2_138948"}],"volume":195,"author":[{"last_name":"Dotterrer","full_name":"Dotterrer, Dominic","first_name":"Dominic"},{"first_name":"Tali","full_name":"Kaufman, Tali","last_name":"Kaufman"},{"orcid":"0000-0002-1494-0568","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","full_name":"Wagner, Uli"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"1378"}]},"day":"01","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"title":"On expansion and topological overlap","article_processing_charge":"Yes (via OA deal)","date_published":"2018-08-01T00:00:00Z","file_date_updated":"2020-07-14T12:47:58Z","language":[{"iso":"eng"}],"type":"journal_article","_id":"742","has_accepted_license":"1","intvolume":"       195","abstract":[{"lang":"eng","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."}],"external_id":{"isi":["000437122700017"]},"date_updated":"2025-06-03T11:41:00Z","year":"2018","date_created":"2018-12-11T11:48:16Z","publication":"Geometriae Dedicata","publist_id":"6925","oa":1,"corr_author":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","department":[{"_id":"UlWa"}]},{"department":[{"_id":"UlWa"}],"publist_id":"6254","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"arxiv":1,"acknowledgement":"An earlier version of the paper appeared in the proceedings of Graph Drawing 2015.  The research of the first author has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no [291734].","date_created":"2018-12-11T11:50:13Z","publication":"Journal of Graph Algorithms and Applications","date_updated":"2025-09-23T09:13:42Z","year":"2017","abstract":[{"lang":"eng","text":"A drawing of a graph G is radial if the vertices of G are placed on concentric circles C 1 , . . . , C k with common center c , and edges are drawn radially : every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Toth."}],"external_id":{"arxiv":["1608.08662"]},"intvolume":"        21","_id":"1113","type":"journal_article","has_accepted_license":"1","file_date_updated":"2019-10-24T10:54:37Z","language":[{"iso":"eng"}],"article_processing_charge":"No","title":"Hanani-Tutte for radial planarity","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_published":"2017-01-01T00:00:00Z","author":[{"orcid":"0000-0001-8485-1774","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav","last_name":"Fulek"},{"full_name":"Pelsmajer, Michael","last_name":"Pelsmajer","first_name":"Michael"},{"full_name":"Schaefer, Marcus","last_name":"Schaefer","first_name":"Marcus"}],"day":"01","related_material":{"record":[{"id":"1164","relation":"earlier_version","status":"public"},{"relation":"earlier_version","status":"public","id":"1595"}]},"project":[{"call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme"}],"publisher":"Brown University","volume":21,"file":[{"file_name":"2017_JournalGraphAlgorithms_Fulek.pdf","access_level":"open_access","file_size":573623,"relation":"main_file","content_type":"application/pdf","file_id":"6967","date_updated":"2019-10-24T10:54:37Z","date_created":"2019-10-24T10:54:37Z","creator":"dernst","success":1}],"citation":{"ista":"Fulek R, Pelsmajer M, Schaefer M. 2017. Hanani-Tutte for radial planarity. Journal of Graph Algorithms and Applications. 21(1), 135–154.","chicago":"Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte for Radial Planarity.” <i>Journal of Graph Algorithms and Applications</i>. Brown University, 2017. <a href=\"https://doi.org/10.7155/jgaa.00408\">https://doi.org/10.7155/jgaa.00408</a>.","ama":"Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity. <i>Journal of Graph Algorithms and Applications</i>. 2017;21(1):135-154. doi:<a href=\"https://doi.org/10.7155/jgaa.00408\">10.7155/jgaa.00408</a>","mla":"Fulek, Radoslav, et al. “Hanani-Tutte for Radial Planarity.” <i>Journal of Graph Algorithms and Applications</i>, vol. 21, no. 1, Brown University, 2017, pp. 135–54, doi:<a href=\"https://doi.org/10.7155/jgaa.00408\">10.7155/jgaa.00408</a>.","short":"R. Fulek, M. Pelsmajer, M. Schaefer, Journal of Graph Algorithms and Applications 21 (2017) 135–154.","apa":"Fulek, R., Pelsmajer, M., &#38; Schaefer, M. (2017). Hanani-Tutte for radial planarity. <i>Journal of Graph Algorithms and Applications</i>. Brown University. <a href=\"https://doi.org/10.7155/jgaa.00408\">https://doi.org/10.7155/jgaa.00408</a>","ieee":"R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity,” <i>Journal of Graph Algorithms and Applications</i>, vol. 21, no. 1. Brown University, pp. 135–154, 2017."},"page":"135 - 154","publication_status":"published","ec_funded":1,"scopus_import":"1","month":"01","article_type":"original","oa_version":"Published Version","status":"public","issue":"1","ddc":["510"],"doi":"10.7155/jgaa.00408","quality_controlled":"1"}]