[{"date_published":"2020-06-01T00:00:00Z","scopus_import":1,"license":"https://creativecommons.org/licenses/by/4.0/","date_created":"2020-06-22T09:14:19Z","conference":{"location":"Zürich, Switzerland","start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry","end_date":"2020-06-26"},"_id":"7990","author":[{"first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Welzl, Emo","first_name":"Emo","last_name":"Welzl"}],"abstract":[{"text":"Given a finite point set P in general position in the plane, a full triangulation is a maximal straight-line embedded plane graph on P. A partial triangulation on P is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge, removes a non-extreme point of degree 3, or adds a point in P ⧵ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The goal of this paper is to investigate the structure of this graph, with emphasis on its connectivity. For sets P of n points in general position, we show that the bistellar flip graph is (n-3)-connected, thereby answering, for sets in general position, an open questions raised in a book (by De Loera, Rambau, and Santos) and a survey (by Lee and Santos) on triangulations. This matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points and projecting the lower convex hull), where (n-3)-connectivity has been known since the late 1980s through the secondary polytope (Gelfand, Kapranov, Zelevinsky) and Balinski’s Theorem. Our methods also yield the following results (see the full version [Wagner and Welzl, 2020]): (i) The bistellar flip graph can be covered by graphs of polytopes of dimension n-3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n-3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations are regular iff the trivial subdivision has height n-3 in the partial order of partial subdivisions. (iv) There are arbitrarily large sets P with non-regular partial triangulations, while every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular partial triangulations (answering a question by F. Santos in the unexpected direction).","lang":"eng"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"12129"}]},"publication_status":"published","intvolume":"       164","type":"conference","arxiv":1,"date_updated":"2023-08-04T08:51:07Z","doi":"10.4230/LIPIcs.SoCG.2020.67","year":"2020","ddc":["510"],"month":"06","language":[{"iso":"eng"}],"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"alternative_title":["LIPIcs"],"file":[{"checksum":"3f6925be5f3dcdb3b14cab92f410edf7","access_level":"open_access","date_updated":"2020-07-14T12:48:06Z","date_created":"2020-06-23T06:37:27Z","creator":"dernst","file_id":"8003","file_name":"2020_LIPIcsSoCG_Wagner.pdf","content_type":"application/pdf","relation":"main_file","file_size":793187}],"oa_version":"Published Version","volume":164,"quality_controlled":"1","publication_identifier":{"isbn":["9783959771436"],"issn":["18688969"]},"article_number":"67:1 - 67:16","day":"01","oa":1,"citation":{"ista":"Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 67:1-67:16.","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips).” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 67:1-67:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.67\">10.4230/LIPIcs.SoCG.2020.67</a>.","ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.67\">10.4230/LIPIcs.SoCG.2020.67</a>","apa":"Wagner, U., &#38; Welzl, E. (2020). Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.67\">https://doi.org/10.4230/LIPIcs.SoCG.2020.67</a>","chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips).” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.67\">https://doi.org/10.4230/LIPIcs.SoCG.2020.67</a>.","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips),” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","short":"U. Wagner, E. Welzl, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020."},"department":[{"_id":"UlWa"}],"status":"public","title":"Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips)","has_accepted_license":"1","file_date_updated":"2020-07-14T12:48:06Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","external_id":{"arxiv":["2003.13557"]},"publication":"36th International Symposium on Computational Geometry","article_processing_charge":"No"},{"month":"06","language":[{"iso":"eng"}],"year":"2020","doi":"10.4230/LIPIcs.SoCG.2020.12","ddc":["510"],"date_updated":"2021-01-12T08:16:23Z","type":"conference","arxiv":1,"intvolume":"       164","publication_status":"published","author":[{"full_name":"Avvakumov, Sergey","last_name":"Avvakumov","first_name":"Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Nivasch, Gabriel","last_name":"Nivasch","first_name":"Gabriel"}],"abstract":[{"lang":"eng","text":"We define and study a discrete process that generalizes the convex-layer decomposition of a planar point set. Our process, which we call homotopic curve shortening (HCS), starts with a closed curve (which might self-intersect) in the presence of a set P⊂ ℝ² of point obstacles, and evolves in discrete steps, where each step consists of (1) taking shortcuts around the obstacles, and (2) reducing the curve to its shortest homotopic equivalent. We find experimentally that, if the initial curve is held fixed and P is chosen to be either a very fine regular grid or a uniformly random point set, then HCS behaves at the limit like the affine curve-shortening flow (ACSF). This connection between HCS and ACSF generalizes the link between \"grid peeling\" and the ACSF observed by Eppstein et al. (2017), which applied only to convex curves, and which was studied only for regular grids. We prove that HCS satisfies some properties analogous to those of ACSF: HCS is invariant under affine transformations, preserves convexity, and does not increase the total absolute curvature. Furthermore, the number of self-intersections of a curve, or intersections between two curves (appropriately defined), does not increase. Finally, if the initial curve is simple, then the number of inflection points (appropriately defined) does not increase."}],"date_created":"2020-06-22T09:14:19Z","conference":{"location":"Zürich, Switzerland","start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry","end_date":"2020-06-26"},"_id":"7991","scopus_import":"1","date_published":"2020-06-01T00:00:00Z","license":"https://creativecommons.org/licenses/by/3.0/","publication":"36th International Symposium on Computational Geometry","article_processing_charge":"No","external_id":{"arxiv":["1909.00263"]},"project":[{"name":"Algorithms for Embeddings and Homotopy Theory","grant_number":"P31312","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","status":"public","department":[{"_id":"UlWa"}],"title":"Homotopic curve shortening and the affine curve-shortening flow","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:48:06Z","day":"01","article_number":"12:1 - 12:15","citation":{"apa":"Avvakumov, S., &#38; Nivasch, G. (2020). Homotopic curve shortening and the affine curve-shortening flow. In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.12\">https://doi.org/10.4230/LIPIcs.SoCG.2020.12</a>","ama":"Avvakumov S, Nivasch G. Homotopic curve shortening and the affine curve-shortening flow. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.12\">10.4230/LIPIcs.SoCG.2020.12</a>","mla":"Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the Affine Curve-Shortening Flow.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.12\">10.4230/LIPIcs.SoCG.2020.12</a>.","ista":"Avvakumov S, Nivasch G. 2020. Homotopic curve shortening and the affine curve-shortening flow. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 12:1-12:15.","short":"S. Avvakumov, G. Nivasch, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ieee":"S. Avvakumov and G. Nivasch, “Homotopic curve shortening and the affine curve-shortening flow,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","chicago":"Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the Affine Curve-Shortening Flow.” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.12\">https://doi.org/10.4230/LIPIcs.SoCG.2020.12</a>."},"oa":1,"quality_controlled":"1","publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"file":[{"file_size":575896,"content_type":"application/pdf","relation":"main_file","file_name":"2020_LIPIcsSoCG_Avvakumov.pdf","file_id":"8007","creator":"dernst","date_created":"2020-06-23T11:13:49Z","date_updated":"2020-07-14T12:48:06Z","access_level":"open_access","checksum":"6872df6549142f709fb6354a1b2f2c06"}],"oa_version":"Published Version","volume":164,"tmp":{"name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","image":"/images/cc_by.png","short":"CC BY (3.0)","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode"},"alternative_title":["LIPIcs"]},{"type":"conference","arxiv":1,"date_updated":"2021-01-12T08:16:23Z","publication_status":"published","intvolume":"       164","language":[{"iso":"eng"}],"month":"06","ddc":["510"],"doi":"10.4230/LIPIcs.SoCG.2020.62","year":"2020","conference":{"location":"Zürich, Switzerland","start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry","end_date":"2020-06-26"},"_id":"7992","date_created":"2020-06-22T09:14:20Z","date_published":"2020-06-01T00:00:00Z","scopus_import":1,"author":[{"orcid":"0000-0002-3975-1683","last_name":"Patakova","first_name":"Zuzana","full_name":"Patakova, Zuzana","id":"48B57058-F248-11E8-B48F-1D18A9856A87"},{"id":"38AC689C-F248-11E8-B48F-1D18A9856A87","full_name":"Tancer, Martin","orcid":"0000-0002-1191-6714","last_name":"Tancer","first_name":"Martin"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli"}],"abstract":[{"lang":"eng","text":"Let K be a convex body in ℝⁿ (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K ∩ h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p₀ is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question. It follows from known results that for n ≥ 2, there are always at least three distinct barycentric cuts through the point p₀ ∈ K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p₀ are guaranteed if n ≥ 3."}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2020-07-14T12:48:06Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","has_accepted_license":"1","department":[{"_id":"UlWa"}],"title":"Barycentric cuts through a convex body","status":"public","article_processing_charge":"No","publication":"36th International Symposium on Computational Geometry","external_id":{"arxiv":["2003.13536"]},"oa_version":"Published Version","volume":164,"file":[{"file_id":"8004","creator":"dernst","relation":"main_file","content_type":"application/pdf","file_name":"2020_LIPIcsSoCG_Patakova.pdf","file_size":750318,"checksum":"ce1c9194139a664fb59d1efdfc88eaae","access_level":"open_access","date_updated":"2020-07-14T12:48:06Z","date_created":"2020-06-23T06:45:52Z"}],"alternative_title":["LIPIcs"],"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"oa":1,"citation":{"short":"Z. Patakova, M. Tancer, U. Wagner, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","chicago":"Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through a Convex Body.” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.62\">https://doi.org/10.4230/LIPIcs.SoCG.2020.62</a>.","ieee":"Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex body,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","mla":"Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 62:1-62:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.62\">10.4230/LIPIcs.SoCG.2020.62</a>.","ama":"Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.62\">10.4230/LIPIcs.SoCG.2020.62</a>","apa":"Patakova, Z., Tancer, M., &#38; Wagner, U. (2020). Barycentric cuts through a convex body. In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.62\">https://doi.org/10.4230/LIPIcs.SoCG.2020.62</a>","ista":"Patakova Z, Tancer M, Wagner U. 2020. Barycentric cuts through a convex body. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 62:1-62:16."},"article_number":"62:1 - 62:16","day":"01","publication_identifier":{"isbn":["9783959771436"],"issn":["18688969"]},"quality_controlled":"1"},{"external_id":{"arxiv":["1804.09317"]},"project":[{"name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","call_identifier":"H2020"}],"publication":"36th International Symposium on Computational Geometry","article_processing_charge":"No","has_accepted_license":"1","department":[{"_id":"UlWa"}],"status":"public","title":"Extending drawings of graphs to arrangements of pseudolines","file_date_updated":"2020-07-14T12:48:06Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"article_number":"9:1 - 9:14","day":"01","oa":1,"citation":{"apa":"Arroyo Guevara, A. M., Bensmail, J., &#38; Bruce Richter, R. (2020). Extending drawings of graphs to arrangements of pseudolines. In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.9\">https://doi.org/10.4230/LIPIcs.SoCG.2020.9</a>","mla":"Arroyo Guevara, Alan M., et al. “Extending Drawings of Graphs to Arrangements of Pseudolines.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.9\">10.4230/LIPIcs.SoCG.2020.9</a>.","ama":"Arroyo Guevara AM, Bensmail J, Bruce Richter R. Extending drawings of graphs to arrangements of pseudolines. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.9\">10.4230/LIPIcs.SoCG.2020.9</a>","ista":"Arroyo Guevara AM, Bensmail J, Bruce Richter R. 2020. Extending drawings of graphs to arrangements of pseudolines. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 9:1-9:14.","short":"A.M. Arroyo Guevara, J. Bensmail, R. Bruce Richter, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","chicago":"Arroyo Guevara, Alan M, Julien Bensmail, and R. Bruce Richter. “Extending Drawings of Graphs to Arrangements of Pseudolines.” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.9\">https://doi.org/10.4230/LIPIcs.SoCG.2020.9</a>.","ieee":"A. M. Arroyo Guevara, J. Bensmail, and R. Bruce Richter, “Extending drawings of graphs to arrangements of pseudolines,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164."},"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"alternative_title":["LIPIcs"],"file":[{"file_size":592661,"creator":"dernst","file_id":"8006","file_name":"2020_LIPIcsSoCG_Arroyo.pdf","relation":"main_file","content_type":"application/pdf","date_updated":"2020-07-14T12:48:06Z","date_created":"2020-06-23T11:06:23Z","access_level":"open_access","checksum":"93571b76cf97d5b7c8aabaeaa694dd7e"}],"volume":164,"oa_version":"Published Version","doi":"10.4230/LIPIcs.SoCG.2020.9","year":"2020","ddc":["510"],"month":"06","language":[{"iso":"eng"}],"publication_status":"published","intvolume":"       164","arxiv":1,"type":"conference","date_updated":"2023-02-23T13:22:12Z","ec_funded":1,"abstract":[{"text":"In the recent study of crossing numbers, drawings of graphs that can be extended to an arrangement of pseudolines (pseudolinear drawings) have played an important role as they are a natural combinatorial extension of rectilinear (or straight-line) drawings. A characterization of the pseudolinear drawings of K_n was found recently. We extend this characterization to all graphs, by describing the set of minimal forbidden subdrawings for pseudolinear drawings. Our characterization also leads to a polynomial-time algorithm to recognize pseudolinear drawings and construct the pseudolines when it is possible.","lang":"eng"}],"author":[{"last_name":"Arroyo Guevara","orcid":"0000-0003-2401-8670","first_name":"Alan M","full_name":"Arroyo Guevara, Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Bensmail, Julien","first_name":"Julien","last_name":"Bensmail"},{"full_name":"Bruce Richter, R.","first_name":"R.","last_name":"Bruce Richter"}],"date_published":"2020-06-01T00:00:00Z","scopus_import":"1","date_created":"2020-06-22T09:14:21Z","_id":"7994","conference":{"start_date":"2020-06-22","location":"Zürich, Switzerland","name":"SoCG: Symposium on Computational Geometry","end_date":"2020-06-26"}},{"abstract":[{"lang":"eng","text":"Algorithms in computational 3-manifold topology typically take a triangulation as an input and return topological information about the underlying 3-manifold. However, extracting the desired information from a triangulation (e.g., evaluating an invariant) is often computationally very expensive. In recent years this complexity barrier has been successfully tackled in some cases by importing ideas from the theory of parameterized algorithms into the realm of 3-manifolds. Various computationally hard problems were shown to be efficiently solvable for input triangulations that are sufficiently “tree-like.”\r\nIn this thesis we focus on the key combinatorial parameter in the above context: we consider the treewidth of a compact, orientable 3-manifold, i.e., the smallest treewidth of the dual graph of any triangulation thereof. By building on the work of Scharlemann–Thompson and Scharlemann–Schultens–Saito on generalized Heegaard splittings, and on the work of Jaco–Rubinstein on layered triangulations, we establish quantitative relations between the treewidth and classical topological invariants of a 3-manifold. In particular, among other results, we show that the treewidth of a closed, orientable, irreducible, non-Haken 3-manifold is always within a constant factor of its Heegaard genus."}],"author":[{"orcid":"0000-0002-5445-5057","last_name":"Huszár","first_name":"Kristóf","full_name":"Huszár, Kristóf","id":"33C26278-F248-11E8-B48F-1D18A9856A87"}],"supervisor":[{"last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Jonathan","last_name":"Spreer","full_name":"Spreer, Jonathan"}],"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"6556"},{"id":"7093","relation":"dissertation_contains","status":"public"}]},"date_published":"2020-06-26T00:00:00Z","date_created":"2020-06-26T10:00:36Z","degree_awarded":"PhD","_id":"8032","doi":"10.15479/AT:ISTA:8032","year":"2020","ddc":["514"],"month":"06","language":[{"iso":"eng"}],"publication_status":"published","acknowledged_ssus":[{"_id":"E-Lib"},{"_id":"CampIT"}],"type":"dissertation","date_updated":"2023-09-07T13:18:27Z","publication_identifier":{"isbn":["978-3-99078-006-0"],"issn":["2663-337X"]},"day":"26","oa":1,"citation":{"chicago":"Huszár, Kristóf. “Combinatorial Width Parameters for 3-Dimensional Manifolds.” Institute of Science and Technology Austria, 2020. <a href=\"https://doi.org/10.15479/AT:ISTA:8032\">https://doi.org/10.15479/AT:ISTA:8032</a>.","ieee":"K. Huszár, “Combinatorial width parameters for 3-dimensional manifolds,” Institute of Science and Technology Austria, 2020.","short":"K. Huszár, Combinatorial Width Parameters for 3-Dimensional Manifolds, Institute of Science and Technology Austria, 2020.","ista":"Huszár K. 2020. Combinatorial width parameters for 3-dimensional manifolds. Institute of Science and Technology Austria.","mla":"Huszár, Kristóf. <i>Combinatorial Width Parameters for 3-Dimensional Manifolds</i>. Institute of Science and Technology Austria, 2020, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:8032\">10.15479/AT:ISTA:8032</a>.","ama":"Huszár K. Combinatorial width parameters for 3-dimensional manifolds. 2020. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:8032\">10.15479/AT:ISTA:8032</a>","apa":"Huszár, K. (2020). <i>Combinatorial width parameters for 3-dimensional manifolds</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:8032\">https://doi.org/10.15479/AT:ISTA:8032</a>"},"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"alternative_title":["ISTA Thesis"],"file":[{"checksum":"bd8be6e4f1addc863dfcc0fad29ee9c3","access_level":"open_access","date_updated":"2020-07-14T12:48:08Z","date_created":"2020-06-26T10:03:58Z","creator":"khuszar","file_id":"8034","content_type":"application/pdf","relation":"main_file","file_name":"Kristof_Huszar-Thesis.pdf","file_size":2637562},{"date_updated":"2020-07-14T12:48:08Z","date_created":"2020-06-26T10:10:06Z","checksum":"d5f8456202b32f4a77552ef47a2837d1","access_level":"closed","file_size":7163491,"file_id":"8035","creator":"khuszar","file_name":"Kristof_Huszar-Thesis-source.zip","relation":"source_file","content_type":"application/x-zip-compressed"}],"oa_version":"Published Version","page":"xviii+120","article_processing_charge":"No","title":"Combinatorial width parameters for 3-dimensional manifolds","has_accepted_license":"1","department":[{"_id":"UlWa"}],"status":"public","file_date_updated":"2020-07-14T12:48:08Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"Institute of Science and Technology Austria"},{"related_material":{"record":[{"id":"8182","status":"public","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","status":"public","id":"8183"},{"id":"8185","status":"public","relation":"part_of_dissertation"},{"status":"public","relation":"part_of_dissertation","id":"8184"},{"relation":"part_of_dissertation","status":"public","id":"6355"},{"id":"75","status":"public","relation":"part_of_dissertation"}]},"author":[{"last_name":"Avvakumov","first_name":"Sergey","full_name":"Avvakumov, Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87"}],"abstract":[{"text":"We present solutions to several problems originating from geometry and discrete mathematics: existence of equipartitions, maps without Tverberg multiple points, and inscribing quadrilaterals. Equivariant obstruction theory is the natural topological approach to these type of questions. However, for the specific problems we consider it had yielded only partial or no results. We get our results by complementing equivariant obstruction theory with other techniques from topology and geometry.","lang":"eng"}],"supervisor":[{"full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"degree_awarded":"PhD","date_created":"2020-07-23T09:51:29Z","_id":"8156","date_published":"2020-07-24T00:00:00Z","month":"07","language":[{"iso":"eng"}],"year":"2020","doi":"10.15479/AT:ISTA:8156","ddc":["514"],"date_updated":"2023-12-18T10:51:01Z","type":"dissertation","publication_status":"published","day":"24","citation":{"apa":"Avvakumov, S. (2020). <i>Topological methods in geometry and discrete mathematics</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:8156\">https://doi.org/10.15479/AT:ISTA:8156</a>","ama":"Avvakumov S. Topological methods in geometry and discrete mathematics. 2020. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:8156\">10.15479/AT:ISTA:8156</a>","mla":"Avvakumov, Sergey. <i>Topological Methods in Geometry and Discrete Mathematics</i>. Institute of Science and Technology Austria, 2020, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:8156\">10.15479/AT:ISTA:8156</a>.","ista":"Avvakumov S. 2020. Topological methods in geometry and discrete mathematics. Institute of Science and Technology Austria.","short":"S. Avvakumov, Topological Methods in Geometry and Discrete Mathematics, Institute of Science and Technology Austria, 2020.","chicago":"Avvakumov, Sergey. “Topological Methods in Geometry and Discrete Mathematics.” Institute of Science and Technology Austria, 2020. <a href=\"https://doi.org/10.15479/AT:ISTA:8156\">https://doi.org/10.15479/AT:ISTA:8156</a>.","ieee":"S. Avvakumov, “Topological methods in geometry and discrete mathematics,” Institute of Science and Technology Austria, 2020."},"oa":1,"publication_identifier":{"issn":["2663-337X"]},"file":[{"date_updated":"2020-07-27T12:44:51Z","date_created":"2020-07-27T12:44:51Z","access_level":"closed","file_size":1061740,"file_id":"8178","creator":"savvakum","file_name":"source.zip","relation":"source_file","content_type":"application/zip"},{"access_level":"open_access","date_updated":"2020-07-27T12:46:53Z","date_created":"2020-07-27T12:46:53Z","success":1,"file_id":"8179","creator":"savvakum","relation":"main_file","content_type":"application/pdf","file_name":"thesis_pdfa.pdf","file_size":1336501}],"page":"119","oa_version":"Published Version","alternative_title":["ISTA Thesis"],"article_processing_charge":"No","publisher":"Institute of Science and Technology Austria","status":"public","has_accepted_license":"1","department":[{"_id":"UlWa"}],"title":"Topological methods in geometry and discrete mathematics","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","file_date_updated":"2020-07-27T12:46:53Z"},{"scopus_import":"1","date_published":"2020-10-09T00:00:00Z","date_created":"2020-11-06T08:45:03Z","_id":"8732","conference":{"start_date":"2020-06-24","location":"Leeds, United Kingdom","end_date":"2020-06-26","name":"WG: Workshop on Graph-Theoretic Concepts in Computer Science"},"ec_funded":1,"author":[{"id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","first_name":"Alan M","orcid":"0000-0003-2401-8670","last_name":"Arroyo Guevara","full_name":"Arroyo Guevara, Alan M"},{"last_name":"Klute","first_name":"Fabian","full_name":"Klute, Fabian"},{"last_name":"Parada","first_name":"Irene","full_name":"Parada, Irene"},{"full_name":"Seidel, Raimund","last_name":"Seidel","first_name":"Raimund"},{"first_name":"Birgit","last_name":"Vogtenhuber","full_name":"Vogtenhuber, Birgit"},{"full_name":"Wiedera, Tilo","first_name":"Tilo","last_name":"Wiedera"}],"abstract":[{"lang":"eng","text":"A simple drawing D(G) of a graph G is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge e in the complement of G can be inserted into D(G) if there exists a simple drawing of   G+e  extending D(G). As a result of Levi’s Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of G can be inserted. In contrast, we show that it is   NP -complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles   A  and a pseudosegment   σ , it can be decided in polynomial time whether there exists a pseudocircle   Φσ  extending   σ  for which   A∪{Φσ}  is again an arrangement of pseudocircles."}],"intvolume":"     12301","publication_status":"published","date_updated":"2023-09-05T15:09:16Z","type":"conference","year":"2020","doi":"10.1007/978-3-030-60440-0_26","month":"10","language":[{"iso":"eng"}],"alternative_title":["LNCS"],"oa_version":"None","volume":12301,"page":"325-338","quality_controlled":"1","publication_identifier":{"isbn":["9783030604394","9783030604400"],"eissn":["1611-3349"],"issn":["0302-9743"]},"day":"09","citation":{"short":"A.M. Arroyo Guevara, F. Klute, I. Parada, R. Seidel, B. Vogtenhuber, T. Wiedera, in:, Graph-Theoretic Concepts in Computer Science, Springer Nature, 2020, pp. 325–338.","ieee":"A. M. Arroyo Guevara, F. Klute, I. Parada, R. Seidel, B. Vogtenhuber, and T. Wiedera, “Inserting one edge into a simple drawing is hard,” in <i>Graph-Theoretic Concepts in Computer Science</i>, Leeds, United Kingdom, 2020, vol. 12301, pp. 325–338.","chicago":"Arroyo Guevara, Alan M, Fabian Klute, Irene Parada, Raimund Seidel, Birgit Vogtenhuber, and Tilo Wiedera. “Inserting One Edge into a Simple Drawing Is Hard.” In <i>Graph-Theoretic Concepts in Computer Science</i>, 12301:325–38. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-60440-0_26\">https://doi.org/10.1007/978-3-030-60440-0_26</a>.","ama":"Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T. Inserting one edge into a simple drawing is hard. In: <i>Graph-Theoretic Concepts in Computer Science</i>. Vol 12301. Springer Nature; 2020:325-338. doi:<a href=\"https://doi.org/10.1007/978-3-030-60440-0_26\">10.1007/978-3-030-60440-0_26</a>","mla":"Arroyo Guevara, Alan M., et al. “Inserting One Edge into a Simple Drawing Is Hard.” <i>Graph-Theoretic Concepts in Computer Science</i>, vol. 12301, Springer Nature, 2020, pp. 325–38, doi:<a href=\"https://doi.org/10.1007/978-3-030-60440-0_26\">10.1007/978-3-030-60440-0_26</a>.","apa":"Arroyo Guevara, A. M., Klute, F., Parada, I., Seidel, R., Vogtenhuber, B., &#38; Wiedera, T. (2020). Inserting one edge into a simple drawing is hard. In <i>Graph-Theoretic Concepts in Computer Science</i> (Vol. 12301, pp. 325–338). Leeds, United Kingdom: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-60440-0_26\">https://doi.org/10.1007/978-3-030-60440-0_26</a>","ista":"Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T. 2020. Inserting one edge into a simple drawing is hard. Graph-Theoretic Concepts in Computer Science. WG: Workshop on Graph-Theoretic Concepts in Computer Science, LNCS, vol. 12301, 325–338."},"department":[{"_id":"UlWa"}],"title":"Inserting one edge into a simple drawing is hard","status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"Springer Nature","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"}],"publication":"Graph-Theoretic Concepts in Computer Science","article_processing_charge":"No"},{"quality_controlled":"1","isi":1,"publication_identifier":{"eissn":["16153383"],"issn":["16153375"]},"day":"01","citation":{"ista":"Filakovský M, Vokřínek L. 2020. Are two given maps homotopic? An algorithmic viewpoint. Foundations of Computational Mathematics. 20, 311–330.","mla":"Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An Algorithmic Viewpoint.” <i>Foundations of Computational Mathematics</i>, vol. 20, Springer Nature, 2020, pp. 311–30, doi:<a href=\"https://doi.org/10.1007/s10208-019-09419-x\">10.1007/s10208-019-09419-x</a>.","ama":"Filakovský M, Vokřínek L. Are two given maps homotopic? An algorithmic viewpoint. <i>Foundations of Computational Mathematics</i>. 2020;20:311-330. doi:<a href=\"https://doi.org/10.1007/s10208-019-09419-x\">10.1007/s10208-019-09419-x</a>","apa":"Filakovský, M., &#38; Vokřínek, L. (2020). Are two given maps homotopic? An algorithmic viewpoint. <i>Foundations of Computational Mathematics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10208-019-09419-x\">https://doi.org/10.1007/s10208-019-09419-x</a>","chicago":"Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An Algorithmic Viewpoint.” <i>Foundations of Computational Mathematics</i>. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/s10208-019-09419-x\">https://doi.org/10.1007/s10208-019-09419-x</a>.","ieee":"M. Filakovský and L. Vokřínek, “Are two given maps homotopic? An algorithmic viewpoint,” <i>Foundations of Computational Mathematics</i>, vol. 20. Springer Nature, pp. 311–330, 2020.","short":"M. Filakovský, L. Vokřínek, Foundations of Computational Mathematics 20 (2020) 311–330."},"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1312.2337","open_access":"1"}],"article_type":"original","volume":20,"page":"311-330","oa_version":"Preprint","external_id":{"arxiv":["1312.2337"],"isi":["000522437400004"]},"project":[{"name":"Algorithms for Embeddings and Homotopy Theory","_id":"26611F5C-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P31312"}],"publication":"Foundations of Computational Mathematics","article_processing_charge":"No","department":[{"_id":"UlWa"}],"title":"Are two given maps homotopic? An algorithmic viewpoint","status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"Springer Nature","abstract":[{"text":"This paper presents two algorithms. The first decides the existence of a pointed homotopy between given simplicial maps 𝑓,𝑔:𝑋→𝑌, and the second computes the group [𝛴𝑋,𝑌]∗ of pointed homotopy classes of maps from a suspension; in both cases, the target Y is assumed simply connected. More generally, these algorithms work relative to 𝐴⊆𝑋.","lang":"eng"}],"author":[{"full_name":"Filakovský, Marek","first_name":"Marek","last_name":"Filakovský","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Lukas","last_name":"Vokřínek","full_name":"Vokřínek, Lukas"}],"scopus_import":"1","date_published":"2020-04-01T00:00:00Z","date_created":"2019-06-16T21:59:14Z","_id":"6563","year":"2020","doi":"10.1007/s10208-019-09419-x","month":"04","language":[{"iso":"eng"}],"intvolume":"        20","publication_status":"published","date_updated":"2023-08-17T13:50:44Z","type":"journal_article","arxiv":1},{"date_created":"2024-03-05T08:57:17Z","oa_version":"Published Version","_id":"15082","conference":{"location":"Würzburg, Germany, Virtual","start_date":"2020-03-16","end_date":"2020-03-18","name":"EuroCG: European Workshop on Computational Geometry"},"date_published":"2020-04-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_56.pdf"}],"article_number":"56","day":"01","oa":1,"citation":{"chicago":"Aichholzer, Oswin, Julia Obmann, Pavel Patak, Daniel Perz, and Josef Tkadlec. “Disjoint Tree-Compatible Plane Perfect Matchings.” In <i>36th European Workshop on Computational Geometry</i>, 2020.","ieee":"O. Aichholzer, J. Obmann, P. Patak, D. Perz, and J. Tkadlec, “Disjoint tree-compatible plane perfect matchings,” in <i>36th European Workshop on Computational Geometry</i>, Würzburg, Germany, Virtual, 2020.","short":"O. Aichholzer, J. Obmann, P. Patak, D. Perz, J. Tkadlec, in:, 36th European Workshop on Computational Geometry, 2020.","ista":"Aichholzer O, Obmann J, Patak P, Perz D, Tkadlec J. 2020. Disjoint tree-compatible plane perfect matchings. 36th European Workshop on Computational Geometry. EuroCG: European Workshop on Computational Geometry, 56.","apa":"Aichholzer, O., Obmann, J., Patak, P., Perz, D., &#38; Tkadlec, J. (2020). Disjoint tree-compatible plane perfect matchings. In <i>36th European Workshop on Computational Geometry</i>. Würzburg, Germany, Virtual.","ama":"Aichholzer O, Obmann J, Patak P, Perz D, Tkadlec J. Disjoint tree-compatible plane perfect matchings. In: <i>36th European Workshop on Computational Geometry</i>. ; 2020.","mla":"Aichholzer, Oswin, et al. “Disjoint Tree-Compatible Plane Perfect Matchings.” <i>36th European Workshop on Computational Geometry</i>, 56, 2020."},"abstract":[{"lang":"eng","text":"Two plane drawings of geometric graphs on the same set of points are called disjoint compatible if their union is plane and they do not have an edge in common. For a given set S of 2n points two plane drawings of perfect matchings M1 and M2 (which do not need to be disjoint nor compatible) are disjoint tree-compatible if there exists a plane drawing of a spanning tree T on S which is disjoint compatible to both M1 and M2.\r\nWe show that the graph of all disjoint tree-compatible perfect geometric matchings on 2n points in convex position is connected if and only if 2n ≥ 10. Moreover, in that case the diameter\r\nof this graph is either 4 or 5, independent of n."}],"quality_controlled":"1","author":[{"full_name":"Aichholzer, Oswin","last_name":"Aichholzer","first_name":"Oswin"},{"full_name":"Obmann, Julia","first_name":"Julia","last_name":"Obmann"},{"id":"B593B804-1035-11EA-B4F1-947645A5BB83","full_name":"Patak, Pavel","first_name":"Pavel","last_name":"Patak"},{"last_name":"Perz","first_name":"Daniel","full_name":"Perz, Daniel"},{"id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1097-9684","last_name":"Tkadlec","first_name":"Josef","full_name":"Tkadlec, Josef"}],"type":"conference","date_updated":"2024-03-05T09:00:07Z","publication_status":"published","status":"public","title":"Disjoint tree-compatible plane perfect matchings","department":[{"_id":"KrCh"},{"_id":"UlWa"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"36th European Workshop on Computational Geometry","month":"04","language":[{"iso":"eng"}],"article_processing_charge":"No","acknowledgement":"Research on this work was initiated at the 6th Austrian-Japanese-Mexican-Spanish Workshop on Discrete Geometry and continued during the 16th European Geometric Graph-Week, both held near Strobl, Austria. We are grateful to the participants for the inspiring atmosphere. We especially thank Alexander Pilz for bringing this class of problems to our attention and Birgit Vogtenhuber for inspiring discussions. D.P. is partially supported by the FWF grant I 3340-N35 (Collaborative DACH project Arrangements and Drawings). The research stay of P.P. at IST Austria is funded by the project CZ.02.2.69/0.0/0.0/17_050/0008466 Improvement of internationalization in the field of research and development at Charles University, through the support of quality projects MSCA-IF. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922.","year":"2020"},{"acknowledgement":"This research was carried out with the support of the Russian Foundation for Basic Research(grant no. 19-01-00169)","external_id":{"isi":["000625983100001"],"arxiv":["1511.03501"]},"publication":"Russian Mathematical Surveys","article_processing_charge":"No","department":[{"_id":"UlWa"}],"status":"public","title":"Eliminating higher-multiplicity intersections, III. Codimension 2","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"IOP Publishing","isi":1,"quality_controlled":"1","publication_identifier":{"issn":["0036-0279"]},"day":"01","oa":1,"citation":{"ista":"Avvakumov S, Wagner U, Mabillard I, Skopenkov AB. 2020. Eliminating higher-multiplicity intersections, III. Codimension 2. Russian Mathematical Surveys. 75(6), 1156–1158.","ama":"Avvakumov S, Wagner U, Mabillard I, Skopenkov AB. Eliminating higher-multiplicity intersections, III. Codimension 2. <i>Russian Mathematical Surveys</i>. 2020;75(6):1156-1158. doi:<a href=\"https://doi.org/10.1070/RM9943\">10.1070/RM9943</a>","mla":"Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” <i>Russian Mathematical Surveys</i>, vol. 75, no. 6, IOP Publishing, 2020, pp. 1156–58, doi:<a href=\"https://doi.org/10.1070/RM9943\">10.1070/RM9943</a>.","apa":"Avvakumov, S., Wagner, U., Mabillard, I., &#38; Skopenkov, A. B. (2020). Eliminating higher-multiplicity intersections, III. Codimension 2. <i>Russian Mathematical Surveys</i>. IOP Publishing. <a href=\"https://doi.org/10.1070/RM9943\">https://doi.org/10.1070/RM9943</a>","ieee":"S. Avvakumov, U. Wagner, I. Mabillard, and A. B. Skopenkov, “Eliminating higher-multiplicity intersections, III. Codimension 2,” <i>Russian Mathematical Surveys</i>, vol. 75, no. 6. IOP Publishing, pp. 1156–1158, 2020.","chicago":"Avvakumov, Sergey, Uli Wagner, Isaac Mabillard, and A. B. Skopenkov. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” <i>Russian Mathematical Surveys</i>. IOP Publishing, 2020. <a href=\"https://doi.org/10.1070/RM9943\">https://doi.org/10.1070/RM9943</a>.","short":"S. Avvakumov, U. Wagner, I. Mabillard, A.B. Skopenkov, Russian Mathematical Surveys 75 (2020) 1156–1158."},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1511.03501"}],"page":"1156-1158","oa_version":"Preprint","volume":75,"article_type":"original","doi":"10.1070/RM9943","year":"2020","month":"12","language":[{"iso":"eng"}],"publication_status":"published","intvolume":"        75","type":"journal_article","arxiv":1,"date_updated":"2023-08-14T11:43:54Z","author":[{"last_name":"Avvakumov","first_name":"Sergey","full_name":"Avvakumov, Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Mabillard, Isaac","last_name":"Mabillard","first_name":"Isaac","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Skopenkov, A. B.","first_name":"A. B.","last_name":"Skopenkov"}],"issue":"6","related_material":{"record":[{"id":"8183","relation":"earlier_version","status":"public"},{"relation":"later_version","status":"public","id":"10220"}]},"date_published":"2020-12-01T00:00:00Z","scopus_import":"1","date_created":"2021-04-04T22:01:22Z","_id":"9308"},{"year":"2019","external_id":{"arxiv":["1903.06981"]},"article_processing_charge":"No","language":[{"iso":"eng"}],"month":"03","publication":"arXiv","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","title":"Token swapping on trees","department":[{"_id":"HeEd"},{"_id":"UlWa"},{"_id":"KrCh"}],"publication_status":"submitted","date_updated":"2024-01-04T12:42:08Z","type":"preprint","arxiv":1,"author":[{"first_name":"Ahmad","last_name":"Biniaz","full_name":"Biniaz, Ahmad"},{"last_name":"Jain","first_name":"Kshitij","full_name":"Jain, Kshitij"},{"full_name":"Lubiw, Anna","last_name":"Lubiw","first_name":"Anna"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322","last_name":"Masárová","first_name":"Zuzana","full_name":"Masárová, Zuzana"},{"first_name":"Tillmann","last_name":"Miltzow","full_name":"Miltzow, Tillmann"},{"first_name":"Debajyoti","last_name":"Mondal","full_name":"Mondal, Debajyoti"},{"last_name":"Naredla","first_name":"Anurag Murty","full_name":"Naredla, Anurag Murty"},{"id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","full_name":"Tkadlec, Josef","first_name":"Josef","last_name":"Tkadlec","orcid":"0000-0002-1097-9684"},{"full_name":"Turcotte, Alexi","last_name":"Turcotte","first_name":"Alexi"}],"abstract":[{"text":"The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex.  The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete.  We present some partial results:\r\n1.  An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan.\r\n2.  Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3.  Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2.\r\n3.  A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars.  In this version, tokens and  vertices  have  colours,  and  colours  have  weights.   The  goal  is  to  get  every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.","lang":"eng"}],"citation":{"apa":"Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte, A. (n.d.). Token swapping on trees. <i>arXiv</i>.","mla":"Biniaz, Ahmad, et al. “Token Swapping on Trees.” <i>ArXiv</i>, 1903.06981.","ama":"Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. <i>arXiv</i>.","ista":"Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec J, Turcotte A. Token swapping on trees. arXiv, 1903.06981.","short":"A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec, A. Turcotte, ArXiv (n.d.).","ieee":"A. Biniaz <i>et al.</i>, “Token swapping on trees,” <i>arXiv</i>. .","chicago":"Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token Swapping on Trees.” <i>ArXiv</i>, n.d."},"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"7944"},{"status":"public","relation":"later_version","id":"12833"}]},"oa":1,"day":"16","article_number":"1903.06981","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1903.06981"}],"date_published":"2019-03-16T00:00:00Z","_id":"7950","oa_version":"Preprint","date_created":"2020-06-08T12:25:25Z"},{"date_updated":"2023-09-07T13:12:17Z","type":"preprint","arxiv":1,"publisher":"arXiv","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Vanishing of all equivariant obstructions and the mapping degree","status":"public","department":[{"_id":"UlWa"}],"publication_status":"submitted","article_processing_charge":"No","language":[{"iso":"eng"}],"publication":"arXiv","month":"10","project":[{"name":"Algorithms for Embeddings and Homotopy Theory","_id":"26611F5C-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P31312"}],"year":"2019","external_id":{"arxiv":["1910.12628"]},"_id":"8182","oa_version":"Preprint","date_created":"2020-07-30T10:45:08Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1910.12628"}],"date_published":"2019-10-28T00:00:00Z","citation":{"ista":"Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping degree. arXiv, 1910.12628.","ama":"Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping degree. <i>arXiv</i>.","mla":"Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions and the Mapping Degree.” <i>ArXiv</i>, 1910.12628, arXiv.","apa":"Avvakumov, S., &#38; Kudrya, S. (n.d.). Vanishing of all equivariant obstructions and the mapping degree. <i>arXiv</i>. arXiv.","chicago":"Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions and the Mapping Degree.” <i>ArXiv</i>. arXiv, n.d.","ieee":"S. Avvakumov and S. Kudrya, “Vanishing of all equivariant obstructions and the mapping degree,” <i>arXiv</i>. arXiv.","short":"S. Avvakumov, S. Kudrya, ArXiv (n.d.)."},"oa":1,"related_material":{"record":[{"id":"11446","status":"public","relation":"later_version"},{"relation":"dissertation_contains","status":"public","id":"8156"}]},"day":"28","article_number":"1910.12628","author":[{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","last_name":"Avvakumov","first_name":"Sergey","full_name":"Avvakumov, Sergey"},{"id":"ecf01965-d252-11ea-95a5-8ada5f6c6a67","last_name":"Kudrya","first_name":"Sergey","full_name":"Kudrya, Sergey"}],"abstract":[{"lang":"eng","text":"Suppose that $n\\neq p^k$ and $n\\neq 2p^k$ for all $k$ and all primes $p$. We prove that for any Hausdorff compactum $X$ with a free action of the symmetric group $\\mathfrak S_n$ there exists an $\\mathfrak S_n$-equivariant map $X \\to\r\n{\\mathbb R}^n$ whose image avoids the diagonal $\\{(x,x\\dots,x)\\in {\\mathbb R}^n|x\\in {\\mathbb R}\\}$.\r\n  Previously, the special cases of this statement for certain $X$ were usually proved using the equivartiant obstruction theory. Such calculations are difficult and may become infeasible past the first (primary) obstruction. We\r\ntake a different approach which allows us to prove the vanishing of all obstructions simultaneously. The essential step in the proof is classifying the possible degrees of $\\mathfrak S_n$-equivariant maps from the boundary\r\n$\\partial\\Delta^{n-1}$ of $(n-1)$-simplex to itself.  Existence of equivariant maps between spaces is important for many questions arising from discrete mathematics and geometry, such as Kneser's conjecture, the Square Peg conjecture, the Splitting Necklace problem, and the Topological Tverberg conjecture, etc. We demonstrate the utility of our result  applying it to one such question, a specific instance of envy-free division problem."}]},{"language":[{"iso":"eng"}],"article_processing_charge":"No","publication":"arXiv","month":"08","project":[{"grant_number":"P31312","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory"}],"external_id":{"isi":["000986519600004"],"arxiv":["1908.08731"]},"acknowledgement":"We would like to thank F. Frick for helpful discussions","year":"2019","type":"preprint","arxiv":1,"date_updated":"2023-09-08T11:20:02Z","publisher":"arXiv","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_status":"submitted","status":"public","department":[{"_id":"UlWa"}],"title":"Stronger counterexamples to the topological Tverberg conjecture","oa":1,"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"8156"}]},"citation":{"short":"S. Avvakumov, R. Karasev, A. Skopenkov, ArXiv (n.d.).","ieee":"S. Avvakumov, R. Karasev, and A. Skopenkov, “Stronger counterexamples to the topological Tverberg conjecture,” <i>arXiv</i>. arXiv.","chicago":"Avvakumov, Sergey, R. Karasev, and A. Skopenkov. “Stronger Counterexamples to the Topological Tverberg Conjecture.” <i>ArXiv</i>. arXiv, n.d.","apa":"Avvakumov, S., Karasev, R., &#38; Skopenkov, A. (n.d.). Stronger counterexamples to the topological Tverberg conjecture. <i>arXiv</i>. arXiv.","ama":"Avvakumov S, Karasev R, Skopenkov A. Stronger counterexamples to the topological Tverberg conjecture. <i>arXiv</i>.","mla":"Avvakumov, Sergey, et al. “Stronger Counterexamples to the Topological Tverberg Conjecture.” <i>ArXiv</i>, 1908.08731, arXiv.","ista":"Avvakumov S, Karasev R, Skopenkov A. Stronger counterexamples to the topological Tverberg conjecture. arXiv, 1908.08731."},"article_number":"1908.08731","day":"23","isi":1,"author":[{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey","last_name":"Avvakumov","full_name":"Avvakumov, Sergey"},{"last_name":"Karasev","first_name":"R.","full_name":"Karasev, R."},{"full_name":"Skopenkov, A.","first_name":"A.","last_name":"Skopenkov"}],"abstract":[{"lang":"eng","text":"Denote by ∆N the N-dimensional simplex. A map f : ∆N → Rd is an almost r-embedding if fσ1∩. . .∩fσr = ∅ whenever σ1, . . . , σr are pairwise disjoint faces. A counterexample to the topological Tverberg conjecture asserts that if r is not a prime power and d ≥ 2r + 1, then there is an almost r-embedding ∆(d+1)(r−1) → Rd. This was improved by Blagojevi´c–Frick–Ziegler using a simple construction of higher-dimensional counterexamples by taking k-fold join power of lower-dimensional ones. We improve this further (for d large compared to r): If r is not a prime power and N := (d+ 1)r−r l\r\nd + 2 r + 1 m−2, then there is an almost r-embedding ∆N → Rd. For the r-fold van Kampen–Flores conjecture we also produce counterexamples which are stronger than previously known. Our proof is based on generalizations of the Mabillard–Wagner theorem on construction of almost r-embeddings from equivariant maps, and of the Ozaydin theorem on existence of equivariant maps. "}],"oa_version":"Preprint","_id":"8184","date_created":"2020-07-30T10:45:34Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1908.08731"}],"date_published":"2019-08-23T00:00:00Z"},{"date_published":"2019-07-25T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1907.11183"}],"date_created":"2020-07-30T10:45:51Z","oa_version":"Preprint","_id":"8185","abstract":[{"text":"In this paper we study envy-free division problems. The classical approach to some of such problems, used by David Gale, reduces to considering continuous maps of a simplex to itself and finding sufficient conditions when this map hits the center of the simplex. The mere continuity is not sufficient for such a conclusion, the usual assumption (for example, in the Knaster--Kuratowski--Mazurkiewicz and the Gale theorem) is a certain boundary condition.\r\n  We follow Erel Segal-Halevi, Fr\\'ed\\'eric Meunier, and Shira Zerbib, and replace the boundary condition by another assumption, which has the economic meaning of possibility for a player to prefer an empty part in the segment\r\npartition problem. We solve the problem positively when $n$, the number of players that divide the segment, is a prime power, and we provide counterexamples for every $n$ which is not a prime power. We also provide counterexamples relevant to a wider class of fair or envy-free partition problems when $n$ is odd and not a prime power.","lang":"eng"}],"author":[{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey","last_name":"Avvakumov","full_name":"Avvakumov, Sergey"},{"full_name":"Karasev, Roman","last_name":"Karasev","first_name":"Roman"}],"article_number":"1907.11183","day":"25","oa":1,"related_material":{"link":[{"relation":"later_version","url":"https://doi.org/10.1112/mtk.12059"}],"record":[{"id":"8156","relation":"dissertation_contains","status":"public"}]},"citation":{"ista":"Avvakumov S, Karasev R. Envy-free division using mapping degree. arXiv, 1907.11183.","apa":"Avvakumov, S., &#38; Karasev, R. (n.d.). Envy-free division using mapping degree. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.1907.11183\">https://doi.org/10.48550/arXiv.1907.11183</a>","mla":"Avvakumov, Sergey, and Roman Karasev. “Envy-Free Division Using Mapping Degree.” <i>ArXiv</i>, 1907.11183, doi:<a href=\"https://doi.org/10.48550/arXiv.1907.11183\">10.48550/arXiv.1907.11183</a>.","ama":"Avvakumov S, Karasev R. Envy-free division using mapping degree. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.1907.11183\">10.48550/arXiv.1907.11183</a>","ieee":"S. Avvakumov and R. Karasev, “Envy-free division using mapping degree,” <i>arXiv</i>. .","chicago":"Avvakumov, Sergey, and Roman Karasev. “Envy-Free Division Using Mapping Degree.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.1907.11183\">https://doi.org/10.48550/arXiv.1907.11183</a>.","short":"S. Avvakumov, R. Karasev, ArXiv (n.d.)."},"publication_status":"submitted","department":[{"_id":"UlWa"}],"title":"Envy-free division using mapping degree","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"preprint","arxiv":1,"date_updated":"2023-09-07T13:12:17Z","external_id":{"arxiv":["1907.11183"]},"doi":"10.48550/arXiv.1907.11183","year":"2019","project":[{"call_identifier":"FWF","grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory"}],"month":"07","publication":"arXiv","language":[{"iso":"eng"}],"article_processing_charge":"No"},{"publication":"Discrete Mathematics","article_processing_charge":"No","external_id":{"isi":["000486358100025"],"arxiv":["1901.09955"]},"project":[{"_id":"26366136-B435-11E9-9278-68D0E5697425","name":"Reglas de Conectividad funcional en el hipocampo"},{"name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411"}],"publisher":"Elsevier","title":"Graphs with at most one crossing","department":[{"_id":"UlWa"}],"status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","day":"01","citation":{"ista":"Silva A, Arroyo Guevara AM, Richter B, Lee O. 2019. Graphs with at most one crossing. Discrete Mathematics. 342(11), 3201–3207.","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>.","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>","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>.","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."},"oa":1,"quality_controlled":"1","isi":1,"publication_identifier":{"issn":["0012-365X"]},"oa_version":"Preprint","page":"3201-3207","volume":342,"main_file_link":[{"url":"https://arxiv.org/abs/1901.09955","open_access":"1"}],"month":"11","language":[{"iso":"eng"}],"year":"2019","doi":"10.1016/j.disc.2019.06.031","date_updated":"2023-08-29T06:31:41Z","arxiv":1,"type":"journal_article","intvolume":"       342","publication_status":"published","abstract":[{"text":"The crossing number of a graph G is the least number of crossings over all possible drawings of G. We present a structural characterization of graphs with crossing number one.","lang":"eng"}],"author":[{"last_name":"Silva","first_name":"André ","full_name":"Silva, André "},{"id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","full_name":"Arroyo Guevara, Alan M","last_name":"Arroyo Guevara","orcid":"0000-0003-2401-8670","first_name":"Alan M"},{"first_name":"Bruce","last_name":"Richter","full_name":"Richter, Bruce"},{"last_name":"Lee","first_name":"Orlando","full_name":"Lee, Orlando"}],"ec_funded":1,"issue":"11","date_created":"2019-07-14T21:59:20Z","_id":"6638","scopus_import":"1","date_published":"2019-11-01T00:00:00Z"},{"related_material":{"record":[{"status":"public","relation":"later_version","id":"13974"}]},"abstract":[{"text":"The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2.","lang":"eng"}],"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek","first_name":"Radoslav"},{"full_name":"Gärtner, Bernd","first_name":"Bernd","last_name":"Gärtner"},{"full_name":"Kupavskii, Andrey","last_name":"Kupavskii","first_name":"Andrey"},{"last_name":"Valtr","first_name":"Pavel","full_name":"Valtr, Pavel"},{"full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"_id":"6647","conference":{"name":"SoCG 2019: Symposium on Computational Geometry","end_date":"2019-06-21","location":"Portland, OR, United States","start_date":"2019-06-18"},"date_created":"2019-07-17T10:35:04Z","date_published":"2019-06-01T00:00:00Z","scopus_import":1,"language":[{"iso":"eng"}],"month":"06","ddc":["000","510"],"doi":"10.4230/LIPICS.SOCG.2019.38","year":"2019","arxiv":1,"type":"conference","date_updated":"2023-12-13T12:03:35Z","publication_status":"published","intvolume":"       129","oa":1,"citation":{"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>.","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>","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>","ista":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2019. The crossing Tverberg theorem. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium on Computational Geometry, LIPIcs, vol. 129, 38:1-38:13.","short":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13.","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>.","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."},"day":"01","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771047"]},"quality_controlled":"1","page":"38:1-38:13","volume":129,"oa_version":"Published Version","file":[{"file_size":559837,"file_name":"2019_LIPICS_Fulek.pdf","relation":"main_file","content_type":"application/pdf","file_id":"6667","creator":"dernst","date_created":"2019-07-24T06:54:52Z","date_updated":"2020-07-14T12:47:35Z","access_level":"open_access","checksum":"d6d017f8b41291b94d102294fa96ae9c"}],"alternative_title":["LIPIcs"],"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"publication":"35th International Symposium on Computational Geometry","project":[{"name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"external_id":{"arxiv":["1812.04911"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2020-07-14T12:47:35Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"The crossing Tverberg theorem","department":[{"_id":"UlWa"}],"has_accepted_license":"1","status":"public"},{"day":"08","citation":{"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>","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.","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>.","short":"S.Y. Zhechev, Algorithmic Aspects of Homotopy Theory and Embeddability, Institute of Science and Technology Austria, 2019."},"oa":1,"publication_identifier":{"issn":["2663-337X"]},"file":[{"checksum":"3231e7cbfca3b5687366f84f0a57a0c0","access_level":"open_access","date_updated":"2020-07-14T12:47:37Z","date_created":"2019-08-07T13:02:50Z","file_id":"6771","creator":"szhechev","file_name":"Stephan_Zhechev_thesis.pdf","relation":"main_file","content_type":"application/pdf","file_size":1464227},{"checksum":"85d65eb27b4377a9e332ee37a70f08b6","access_level":"closed","date_updated":"2020-07-14T12:47:37Z","date_created":"2019-08-07T13:03:22Z","file_id":"6772","creator":"szhechev","relation":"source_file","content_type":"application/octet-stream","file_name":"Stephan_Zhechev_thesis.tex","file_size":303988},{"access_level":"closed","checksum":"86b374d264ca2dd53e712728e253ee75","date_created":"2019-08-07T13:03:34Z","date_updated":"2020-07-14T12:47:37Z","relation":"supplementary_material","content_type":"application/zip","file_name":"supplementary_material.zip","creator":"szhechev","file_id":"6773","file_size":1087004}],"oa_version":"Published Version","page":"104","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"alternative_title":["ISTA Thesis"],"article_processing_charge":"No","publisher":"Institute of Science and Technology Austria","title":"Algorithmic aspects of homotopy theory and embeddability","has_accepted_license":"1","department":[{"_id":"UlWa"}],"status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","file_date_updated":"2020-07-14T12:47:37Z","related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"6774"}]},"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."}],"author":[{"last_name":"Zhechev","first_name":"Stephan Y","full_name":"Zhechev, Stephan Y","id":"3AA52972-F248-11E8-B48F-1D18A9856A87"}],"supervisor":[{"first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"degree_awarded":"PhD","date_created":"2019-07-26T11:14:34Z","_id":"6681","date_published":"2019-08-08T00:00:00Z","month":"08","language":[{"iso":"eng"}],"year":"2019","doi":"10.15479/AT:ISTA:6681","ddc":["514"],"date_updated":"2023-09-07T13:10:36Z","type":"dissertation","publication_status":"published"},{"date_created":"2019-11-04T15:45:17Z","_id":"6982","date_published":"2019-10-01T00:00:00Z","scopus_import":1,"related_material":{"record":[{"id":"309","relation":"earlier_version","status":"public"}]},"author":[{"first_name":"Hugo","last_name":"Akitaya","full_name":"Akitaya, Hugo"},{"first_name":"Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Tóth, Csaba","last_name":"Tóth","first_name":"Csaba"}],"abstract":[{"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","lang":"eng"}],"issue":"4","arxiv":1,"type":"journal_article","date_updated":"2023-09-15T12:19:31Z","publication_status":"published","intvolume":"        15","month":"10","language":[{"iso":"eng"}],"doi":"10.1145/3344549","year":"2019","oa_version":"Preprint","volume":15,"article_type":"original","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1709.09209"}],"article_number":"50","day":"01","oa":1,"citation":{"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>","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>.","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>","ista":"Akitaya H, Fulek R, Tóth C. 2019. Recognizing weak embeddings of graphs. ACM Transactions on Algorithms. 15(4), 50.","short":"H. Akitaya, R. Fulek, C. Tóth, ACM Transactions on Algorithms 15 (2019).","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.","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>."},"quality_controlled":"1","publisher":"ACM","title":"Recognizing weak embeddings of graphs","department":[{"_id":"UlWa"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"ACM Transactions on Algorithms","external_id":{"arxiv":["1709.09209"]},"project":[{"_id":"261FA626-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"M02281","name":"Eliminating intersections in drawings of graphs"}]},{"status":"public","department":[{"_id":"UlWa"}],"title":"Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"Springer Nature","external_id":{"isi":["000493267200003"],"arxiv":["1709.00508"]},"project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"},{"name":"Eliminating intersections in drawings of graphs","grant_number":"M02281","call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"publication":"Combinatorica","article_processing_charge":"No","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1709.00508"}],"article_type":"original","oa_version":"Preprint","volume":39,"page":"1267-1279","quality_controlled":"1","isi":1,"publication_identifier":{"eissn":["1439-6912"],"issn":["0209-9683"]},"day":"29","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.","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>.","short":"R. Fulek, J. Kynčl, Combinatorica 39 (2019) 1267–1279.","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.","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>","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>.","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>"},"oa":1,"intvolume":"        39","publication_status":"published","date_updated":"2023-08-30T07:26:25Z","arxiv":1,"type":"journal_article","year":"2019","doi":"10.1007/s00493-019-3905-7","month":"10","language":[{"iso":"eng"}],"scopus_import":"1","date_published":"2019-10-29T00:00:00Z","date_created":"2019-11-18T14:29:50Z","_id":"7034","ec_funded":1,"abstract":[{"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.","lang":"eng"}],"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","full_name":"Fulek, Radoslav"},{"full_name":"Kynčl, Jan","last_name":"Kynčl","first_name":"Jan"}],"issue":"6"},{"file_date_updated":"2020-07-14T12:47:49Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","title":"On the treewidth of triangulated 3-manifolds","department":[{"_id":"UlWa"}],"status":"public","has_accepted_license":"1","publisher":"Computational Geometry Laborartoy","external_id":{"arxiv":["1712.00434"]},"article_processing_charge":"No","publication":"Journal of Computational Geometry","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"volume":10,"oa_version":"Published Version","page":"70–98","article_type":"original","file":[{"date_updated":"2020-07-14T12:47:49Z","date_created":"2019-11-23T12:35:16Z","access_level":"open_access","checksum":"c872d590d38d538404782bca20c4c3f5","file_size":857590,"creator":"khuszar","file_id":"7094","file_name":"479-1917-1-PB.pdf","content_type":"application/pdf","relation":"main_file"}],"publication_identifier":{"issn":["1920-180X"]},"quality_controlled":"1","oa":1,"citation":{"short":"K. Huszár, J. Spreer, U. Wagner, Journal of Computational Geometry 10 (2019) 70–98.","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.","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>.","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>","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>.","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."},"day":"01","publication_status":"published","intvolume":"        10","type":"journal_article","arxiv":1,"date_updated":"2023-09-07T13:18:26Z","ddc":["514"],"doi":"10.20382/JOGC.V10I2A5","year":"2019","language":[{"iso":"eng"}],"month":"11","date_published":"2019-11-01T00:00:00Z","_id":"7093","date_created":"2019-11-23T12:14:09Z","issue":"2","abstract":[{"lang":"eng","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))."}],"author":[{"id":"33C26278-F248-11E8-B48F-1D18A9856A87","first_name":"Kristóf","last_name":"Huszár","orcid":"0000-0002-5445-5057","full_name":"Huszár, Kristóf"},{"full_name":"Spreer, Jonathan","first_name":"Jonathan","last_name":"Spreer"},{"last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"285"},{"id":"8032","status":"public","relation":"part_of_dissertation"}]}}]