[{"external_id":{"arxiv":["1907.00885"],"isi":["000537329400001"]},"abstract":[{"text":"Let A={A1,…,An} be a family of sets in the plane. For 0≤i2b be integers. We prove that if each k-wise or (k+1)-wise intersection of sets from A has at most b path-connected components, which all are open, then fk+1=0 implies fk≤cfk−1 for some positive constant c depending only on b and k. These results also extend to two-dimensional compact surfaces.","lang":"eng"}],"publication_status":"published","department":[{"_id":"UlWa"}],"page":"304-323","volume":64,"quality_controlled":"1","publisher":"Springer Nature","date_published":"2020-09-01T00:00:00Z","date_created":"2020-06-14T22:00:50Z","citation":{"apa":"Kalai, G., & Patakova, Z. (2020). Intersection patterns of planar sets. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00205-z","chicago":"Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.” Discrete and Computational Geometry. Springer Nature, 2020. https://doi.org/10.1007/s00454-020-00205-z.","mla":"Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.” Discrete and Computational Geometry, vol. 64, Springer Nature, 2020, pp. 304–23, doi:10.1007/s00454-020-00205-z.","ista":"Kalai G, Patakova Z. 2020. Intersection patterns of planar sets. Discrete and Computational Geometry. 64, 304–323.","ieee":"G. Kalai and Z. Patakova, “Intersection patterns of planar sets,” Discrete and Computational Geometry, vol. 64. Springer Nature, pp. 304–323, 2020.","ama":"Kalai G, Patakova Z. Intersection patterns of planar sets. Discrete and Computational Geometry. 2020;64:304-323. doi:10.1007/s00454-020-00205-z","short":"G. Kalai, Z. Patakova, Discrete and Computational Geometry 64 (2020) 304–323."},"acknowledgement":"We are very grateful to Pavel Paták for many helpful discussions and remarks. We also thank the referees for helpful comments, which greatly improved the presentation.\r\nThe project was supported by ERC Advanced Grant 320924. GK was also partially supported by NSF grant DMS1300120. The research stay of ZP 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.","year":"2020","doi":"10.1007/s00454-020-00205-z","_id":"7960","article_type":"original","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1907.00885"}],"day":"01","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_identifier":{"eissn":["14320444"],"issn":["01795376"]},"month":"09","author":[{"last_name":"Kalai","full_name":"Kalai, Gil","first_name":"Gil"},{"full_name":"Patakova, Zuzana","first_name":"Zuzana","last_name":"Patakova","id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683"}],"arxiv":1,"type":"journal_article","status":"public","intvolume":" 64","scopus_import":"1","isi":1,"title":"Intersection patterns of planar sets","date_updated":"2023-08-21T08:26:34Z","oa":1,"article_processing_charge":"No","publication":"Discrete and Computational Geometry","language":[{"iso":"eng"}]},{"abstract":[{"lang":"eng","text":"We prove general topological Radon-type theorems for sets in ℝ^d, smooth real manifolds or finite dimensional simplicial complexes. Combined with a recent result of Holmsen and Lee, it gives fractional Helly theorem, and consequently the existence of weak ε-nets as well as a (p,q)-theorem. More precisely: Let X be either ℝ^d, smooth real d-manifold, or a finite d-dimensional simplicial complex. Then if F is a finite, intersection-closed family of sets in X such that the ith reduced Betti number (with ℤ₂ coefficients) of any set in F is at most b for every non-negative integer i less or equal to k, then the Radon number of F is bounded in terms of b and X. Here k is the smallest integer larger or equal to d/2 - 1 if X = ℝ^d; k=d-1 if X is a smooth real d-manifold and not a surface, k=0 if X is a surface and k=d if X is a d-dimensional simplicial complex. Using the recent result of the author and Kalai, we manage to prove the following optimal bound on fractional Helly number for families of open sets in a surface: Let F be a finite family of open sets in a surface S such that the intersection of any subfamily of F is either empty, or path-connected. Then the fractional Helly number of F is at most three. This also settles a conjecture of Holmsen, Kim, and Lee about an existence of a (p,q)-theorem for open subsets of a surface."}],"external_id":{"arxiv":["1908.01677"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["510"],"publication_status":"published","volume":164,"quality_controlled":"1","department":[{"_id":"UlWa"}],"date_published":"2020-06-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_number":"61:1-61:13","citation":{"mla":"Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” 36th International Symposium on Computational Geometry, vol. 164, 61:1-61:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.61.","chicago":"Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.61.","ista":"Patakova Z. 2020. Bounding radon number via Betti numbers. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 61:1-61:13.","ieee":"Z. Patakova, “Bounding radon number via Betti numbers,” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","ama":"Patakova Z. Bounding radon number via Betti numbers. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.61","short":"Z. Patakova, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","apa":"Patakova, Z. (2020). Bounding radon number via Betti numbers. In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.61"},"date_created":"2020-06-22T09:14:18Z","year":"2020","doi":"10.4230/LIPIcs.SoCG.2020.61","_id":"7989","file_date_updated":"2020-07-14T12:48:06Z","file":[{"relation":"main_file","content_type":"application/pdf","file_size":645421,"access_level":"open_access","creator":"dernst","date_updated":"2020-07-14T12:48:06Z","date_created":"2020-06-23T06:56:23Z","file_id":"8005","checksum":"d0996ca5f6eb32ce955ce782b4f2afbe","file_name":"2020_LIPIcsSoCG_Patakova_61.pdf"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","day":"01","month":"06","publication_identifier":{"isbn":["9783959771436"],"issn":["18688969"]},"conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2020-06-22","location":"Zürich, Switzerland","end_date":"2020-06-26"},"arxiv":1,"author":[{"full_name":"Patakova, Zuzana","first_name":"Zuzana","orcid":"0000-0002-3975-1683","last_name":"Patakova","id":"48B57058-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","status":"public","alternative_title":["LIPIcs"],"intvolume":" 164","scopus_import":"1","has_accepted_license":"1","title":"Bounding radon number via Betti numbers","article_processing_charge":"No","date_updated":"2021-01-12T08:16:22Z","oa":1,"publication":"36th International Symposium on Computational Geometry","language":[{"iso":"eng"}]},{"oa":1,"date_updated":"2023-08-04T08:51:07Z","article_processing_charge":"No","title":"Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips)","intvolume":" 164","scopus_import":1,"has_accepted_license":"1","language":[{"iso":"eng"}],"publication":"36th International Symposium on Computational Geometry","author":[{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","full_name":"Wagner, Uli","first_name":"Uli"},{"full_name":"Welzl, Emo","first_name":"Emo","last_name":"Welzl"}],"arxiv":1,"conference":{"start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry","end_date":"2020-06-26","location":"Zürich, Switzerland"},"month":"06","publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"day":"01","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"relation":"main_file","file_size":793187,"access_level":"open_access","content_type":"application/pdf","creator":"dernst","date_updated":"2020-07-14T12:48:06Z","date_created":"2020-06-23T06:37:27Z","checksum":"3f6925be5f3dcdb3b14cab92f410edf7","file_id":"8003","file_name":"2020_LIPIcsSoCG_Wagner.pdf"}],"alternative_title":["LIPIcs"],"status":"public","type":"conference","year":"2020","date_created":"2020-06-22T09:14:19Z","citation":{"apa":"Wagner, U., & Welzl, E. (2020). Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.67","short":"U. Wagner, E. Welzl, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips),” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.67","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.","chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips).” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.67.","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips).” 36th International Symposium on Computational Geometry, vol. 164, 67:1-67:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.67."},"article_number":"67:1 - 67:16","related_material":{"record":[{"relation":"later_version","id":"12129","status":"public"}]},"file_date_updated":"2020-07-14T12:48:06Z","_id":"7990","doi":"10.4230/LIPIcs.SoCG.2020.67","publication_status":"published","ddc":["510"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"external_id":{"arxiv":["2003.13557"]},"abstract":[{"lang":"eng","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)."}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2020-06-01T00:00:00Z","department":[{"_id":"UlWa"}],"quality_controlled":"1","volume":164},{"publication_identifier":{"isbn":["9783959771436"],"issn":["18688969"]},"month":"06","conference":{"end_date":"2020-06-26","location":"Zürich, Switzerland","start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"file_name":"2020_LIPIcsSoCG_Avvakumov.pdf","file_id":"8007","checksum":"6872df6549142f709fb6354a1b2f2c06","date_created":"2020-06-23T11:13:49Z","date_updated":"2020-07-14T12:48:06Z","creator":"dernst","access_level":"open_access","content_type":"application/pdf","file_size":575896,"relation":"main_file"}],"day":"01","oa_version":"Published Version","arxiv":1,"author":[{"last_name":"Avvakumov","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","full_name":"Avvakumov, Sergey","first_name":"Sergey"},{"last_name":"Nivasch","full_name":"Nivasch, Gabriel","first_name":"Gabriel"}],"type":"conference","status":"public","alternative_title":["LIPIcs"],"has_accepted_license":"1","scopus_import":"1","intvolume":" 164","article_processing_charge":"No","oa":1,"date_updated":"2021-01-12T08:16:23Z","title":"Homotopic curve shortening and the affine curve-shortening flow","publication":"36th International Symposium on Computational Geometry","language":[{"iso":"eng"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"ddc":["510"],"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."}],"external_id":{"arxiv":["1909.00263"]},"publication_status":"published","date_published":"2020-06-01T00:00:00Z","license":"https://creativecommons.org/licenses/by/3.0/","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":164,"quality_controlled":"1","department":[{"_id":"UlWa"}],"project":[{"name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","grant_number":"P31312"}],"article_number":"12:1 - 12:15","year":"2020","date_created":"2020-06-22T09:14:19Z","citation":{"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.","chicago":"Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the Affine Curve-Shortening Flow.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.12.","mla":"Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the Affine Curve-Shortening Flow.” 36th International Symposium on Computational Geometry, vol. 164, 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.12.","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 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","ama":"Avvakumov S, Nivasch G. Homotopic curve shortening and the affine curve-shortening flow. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.12","apa":"Avvakumov, S., & Nivasch, G. (2020). Homotopic curve shortening and the affine curve-shortening flow. In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.12"},"doi":"10.4230/LIPIcs.SoCG.2020.12","_id":"7991","file_date_updated":"2020-07-14T12:48:06Z"},{"alternative_title":["LIPIcs"],"type":"conference","status":"public","day":"01","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"checksum":"ce1c9194139a664fb59d1efdfc88eaae","file_name":"2020_LIPIcsSoCG_Patakova.pdf","file_id":"8004","date_created":"2020-06-23T06:45:52Z","date_updated":"2020-07-14T12:48:06Z","creator":"dernst","content_type":"application/pdf","file_size":750318,"relation":"main_file","access_level":"open_access"}],"conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2020-06-22","location":"Zürich, Switzerland","end_date":"2020-06-26"},"publication_identifier":{"isbn":["9783959771436"],"issn":["18688969"]},"month":"06","author":[{"orcid":"0000-0002-3975-1683","last_name":"Patakova","id":"48B57058-F248-11E8-B48F-1D18A9856A87","full_name":"Patakova, Zuzana","first_name":"Zuzana"},{"full_name":"Tancer, Martin","first_name":"Martin","last_name":"Tancer","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1191-6714"},{"full_name":"Wagner, Uli","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner"}],"arxiv":1,"publication":"36th International Symposium on Computational Geometry","language":[{"iso":"eng"}],"has_accepted_license":"1","scopus_import":1,"intvolume":" 164","title":"Barycentric cuts through a convex body","oa":1,"date_updated":"2021-01-12T08:16:23Z","article_processing_charge":"No","department":[{"_id":"UlWa"}],"volume":164,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2020-06-01T00:00:00Z","external_id":{"arxiv":["2003.13536"]},"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."}],"ddc":["510"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publication_status":"published","doi":"10.4230/LIPIcs.SoCG.2020.62","file_date_updated":"2020-07-14T12:48:06Z","_id":"7992","article_number":"62:1 - 62:16","date_created":"2020-06-22T09:14:20Z","citation":{"apa":"Patakova, Z., Tancer, M., & Wagner, U. (2020). Barycentric cuts through a convex body. In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.62","short":"Z. Patakova, M. Tancer, U. Wagner, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ama":"Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.62","ieee":"Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex body,” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","chicago":"Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through a Convex Body.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.62.","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.","mla":"Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” 36th International Symposium on Computational Geometry, vol. 164, 62:1-62:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.62."},"year":"2020"},{"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["510"],"abstract":[{"text":"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"}],"external_id":{"arxiv":["1804.09317"]},"publication_status":"published","date_published":"2020-06-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":164,"quality_controlled":"1","department":[{"_id":"UlWa"}],"project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"}],"article_number":"9:1 - 9:14","ec_funded":1,"year":"2020","date_created":"2020-06-22T09:14:21Z","citation":{"ama":"Arroyo Guevara AM, Bensmail J, Bruce Richter R. Extending drawings of graphs to arrangements of pseudolines. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.9","ieee":"A. M. Arroyo Guevara, J. Bensmail, and R. Bruce Richter, “Extending drawings of graphs to arrangements of pseudolines,” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","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.","mla":"Arroyo Guevara, Alan M., et al. “Extending Drawings of Graphs to Arrangements of Pseudolines.” 36th International Symposium on Computational Geometry, vol. 164, 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.9.","chicago":"Arroyo Guevara, Alan M, Julien Bensmail, and R. Bruce Richter. “Extending Drawings of Graphs to Arrangements of Pseudolines.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.9.","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.","apa":"Arroyo Guevara, A. M., Bensmail, J., & Bruce Richter, R. (2020). Extending drawings of graphs to arrangements of pseudolines. In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.9"},"doi":"10.4230/LIPIcs.SoCG.2020.9","_id":"7994","file_date_updated":"2020-07-14T12:48:06Z","publication_identifier":{"isbn":["9783959771436"],"issn":["18688969"]},"month":"06","conference":{"end_date":"2020-06-26","location":"Zürich, Switzerland","start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"creator":"dernst","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_size":592661,"checksum":"93571b76cf97d5b7c8aabaeaa694dd7e","file_name":"2020_LIPIcsSoCG_Arroyo.pdf","file_id":"8006","date_updated":"2020-07-14T12:48:06Z","date_created":"2020-06-23T11:06:23Z"}],"day":"01","oa_version":"Published Version","arxiv":1,"author":[{"last_name":"Arroyo Guevara","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M","first_name":"Alan M"},{"last_name":"Bensmail","full_name":"Bensmail, Julien","first_name":"Julien"},{"full_name":"Bruce Richter, R.","first_name":"R.","last_name":"Bruce Richter"}],"type":"conference","status":"public","alternative_title":["LIPIcs"],"scopus_import":"1","intvolume":" 164","has_accepted_license":"1","article_processing_charge":"No","date_updated":"2023-02-23T13:22:12Z","oa":1,"title":"Extending drawings of graphs to arrangements of pseudolines","publication":"36th International Symposium on Computational Geometry","language":[{"iso":"eng"}]},{"abstract":[{"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.","lang":"eng"}],"ddc":["514"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publication_status":"published","department":[{"_id":"UlWa"}],"page":"xviii+120","publisher":"Institute of Science and Technology Austria","date_published":"2020-06-26T00:00:00Z","supervisor":[{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli"},{"last_name":"Spreer","full_name":"Spreer, Jonathan","first_name":"Jonathan"}],"degree_awarded":"PhD","related_material":{"record":[{"relation":"dissertation_contains","id":"6556","status":"public"},{"status":"public","id":"7093","relation":"dissertation_contains"}]},"date_created":"2020-06-26T10:00:36Z","citation":{"mla":"Huszár, Kristóf. Combinatorial Width Parameters for 3-Dimensional Manifolds. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:8032.","ista":"Huszár K. 2020. Combinatorial width parameters for 3-dimensional manifolds. Institute of Science and Technology Austria.","chicago":"Huszár, Kristóf. “Combinatorial Width Parameters for 3-Dimensional Manifolds.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:8032.","short":"K. Huszár, Combinatorial Width Parameters for 3-Dimensional Manifolds, Institute of Science and Technology Austria, 2020.","ama":"Huszár K. Combinatorial width parameters for 3-dimensional manifolds. 2020. doi:10.15479/AT:ISTA:8032","ieee":"K. Huszár, “Combinatorial width parameters for 3-dimensional manifolds,” Institute of Science and Technology Austria, 2020.","apa":"Huszár, K. (2020). Combinatorial width parameters for 3-dimensional manifolds. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:8032"},"year":"2020","doi":"10.15479/AT:ISTA:8032","acknowledged_ssus":[{"_id":"E-Lib"},{"_id":"CampIT"}],"file_date_updated":"2020-07-14T12:48:08Z","_id":"8032","day":"26","oa_version":"Published Version","file":[{"date_created":"2020-06-26T10:03:58Z","date_updated":"2020-07-14T12:48:08Z","checksum":"bd8be6e4f1addc863dfcc0fad29ee9c3","file_id":"8034","file_name":"Kristof_Huszar-Thesis.pdf","relation":"main_file","file_size":2637562,"content_type":"application/pdf","access_level":"open_access","creator":"khuszar"},{"file_id":"8035","checksum":"d5f8456202b32f4a77552ef47a2837d1","file_name":"Kristof_Huszar-Thesis-source.zip","date_updated":"2020-07-14T12:48:08Z","date_created":"2020-06-26T10:10:06Z","creator":"khuszar","file_size":7163491,"relation":"source_file","content_type":"application/x-zip-compressed","access_level":"closed"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","month":"06","publication_identifier":{"isbn":["978-3-99078-006-0"],"issn":["2663-337X"]},"author":[{"id":"33C26278-F248-11E8-B48F-1D18A9856A87","last_name":"Huszár","orcid":"0000-0002-5445-5057","full_name":"Huszár, Kristóf","first_name":"Kristóf"}],"alternative_title":["ISTA Thesis"],"type":"dissertation","status":"public","has_accepted_license":"1","title":"Combinatorial width parameters for 3-dimensional manifolds","oa":1,"date_updated":"2023-09-07T13:18:27Z","article_processing_charge":"No","language":[{"iso":"eng"}]},{"article_processing_charge":"No","date_updated":"2023-12-18T10:51:01Z","oa":1,"title":"Topological methods in geometry and discrete mathematics","has_accepted_license":"1","language":[{"iso":"eng"}],"author":[{"last_name":"Avvakumov","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","full_name":"Avvakumov, Sergey","first_name":"Sergey"}],"publication_identifier":{"issn":["2663-337X"]},"month":"07","file":[{"content_type":"application/zip","access_level":"closed","relation":"source_file","file_size":1061740,"creator":"savvakum","date_created":"2020-07-27T12:44:51Z","date_updated":"2020-07-27T12:44:51Z","file_name":"source.zip","file_id":"8178"},{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_size":1336501,"creator":"savvakum","date_created":"2020-07-27T12:46:53Z","date_updated":"2020-07-27T12:46:53Z","success":1,"file_id":"8179","file_name":"thesis_pdfa.pdf"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa_version":"Published Version","day":"24","status":"public","type":"dissertation","alternative_title":["ISTA Thesis"],"year":"2020","date_created":"2020-07-23T09:51:29Z","citation":{"apa":"Avvakumov, S. (2020). Topological methods in geometry and discrete mathematics. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:8156","short":"S. Avvakumov, Topological Methods in Geometry and Discrete Mathematics, Institute of Science and Technology Austria, 2020.","ieee":"S. Avvakumov, “Topological methods in geometry and discrete mathematics,” Institute of Science and Technology Austria, 2020.","ama":"Avvakumov S. Topological methods in geometry and discrete mathematics. 2020. doi:10.15479/AT:ISTA:8156","chicago":"Avvakumov, Sergey. “Topological Methods in Geometry and Discrete Mathematics.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:8156.","mla":"Avvakumov, Sergey. Topological Methods in Geometry and Discrete Mathematics. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:8156.","ista":"Avvakumov S. 2020. Topological methods in geometry and discrete mathematics. Institute of Science and Technology Austria."},"degree_awarded":"PhD","related_material":{"record":[{"status":"public","id":"8182","relation":"part_of_dissertation"},{"status":"public","id":"8183","relation":"part_of_dissertation"},{"id":"8185","relation":"part_of_dissertation","status":"public"},{"id":"8184","relation":"part_of_dissertation","status":"public"},{"status":"public","relation":"part_of_dissertation","id":"6355"},{"status":"public","relation":"part_of_dissertation","id":"75"}]},"_id":"8156","file_date_updated":"2020-07-27T12:46:53Z","doi":"10.15479/AT:ISTA:8156","publication_status":"published","ddc":["514"],"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"}],"date_published":"2020-07-24T00:00:00Z","supervisor":[{"first_name":"Uli","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","orcid":"0000-0002-1494-0568"}],"publisher":"Institute of Science and Technology Austria","department":[{"_id":"UlWa"}],"page":"119"},{"article_number":"56","date_created":"2024-03-05T08:57:17Z","title":"Disjoint tree-compatible plane perfect matchings","citation":{"apa":"Aichholzer, O., Obmann, J., Patak, P., Perz, D., & Tkadlec, J. (2020). Disjoint tree-compatible plane perfect matchings. In 36th European Workshop on Computational Geometry. Würzburg, Germany, Virtual.","mla":"Aichholzer, Oswin, et al. “Disjoint Tree-Compatible Plane Perfect Matchings.” 36th European Workshop on Computational Geometry, 56, 2020.","chicago":"Aichholzer, Oswin, Julia Obmann, Pavel Patak, Daniel Perz, and Josef Tkadlec. “Disjoint Tree-Compatible Plane Perfect Matchings.” 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.","short":"O. Aichholzer, J. Obmann, P. Patak, D. Perz, J. Tkadlec, in:, 36th European Workshop on Computational Geometry, 2020.","ama":"Aichholzer O, Obmann J, Patak P, Perz D, Tkadlec J. Disjoint tree-compatible plane perfect matchings. In: 36th European Workshop on Computational Geometry. ; 2020.","ieee":"O. Aichholzer, J. Obmann, P. Patak, D. Perz, and J. Tkadlec, “Disjoint tree-compatible plane perfect matchings,” in 36th European Workshop on Computational Geometry, Würzburg, Germany, Virtual, 2020."},"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.","date_updated":"2024-03-05T09:00:07Z","oa":1,"year":"2020","article_processing_charge":"No","publication":"36th European Workshop on Computational Geometry","_id":"15082","language":[{"iso":"eng"}],"day":"01","main_file_link":[{"open_access":"1","url":"https://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_56.pdf"}],"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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."}],"conference":{"name":"EuroCG: European Workshop on Computational Geometry","start_date":"2020-03-16","location":"Würzburg, Germany, Virtual","end_date":"2020-03-18"},"month":"04","author":[{"last_name":"Aichholzer","first_name":"Oswin","full_name":"Aichholzer, Oswin"},{"first_name":"Julia","full_name":"Obmann, Julia","last_name":"Obmann"},{"first_name":"Pavel","full_name":"Patak, Pavel","last_name":"Patak","id":"B593B804-1035-11EA-B4F1-947645A5BB83"},{"first_name":"Daniel","full_name":"Perz, Daniel","last_name":"Perz"},{"orcid":"0000-0002-1097-9684","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","first_name":"Josef","full_name":"Tkadlec, Josef"}],"publication_status":"published","department":[{"_id":"KrCh"},{"_id":"UlWa"}],"quality_controlled":"1","type":"conference","date_published":"2020-04-01T00:00:00Z","status":"public"},{"publication_identifier":{"issn":["16153375"],"eissn":["16153383"]},"month":"04","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1312.2337"}],"day":"01","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","author":[{"full_name":"Filakovský, Marek","first_name":"Marek","last_name":"Filakovský","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Lukas","full_name":"Vokřínek, Lukas","last_name":"Vokřínek"}],"arxiv":1,"status":"public","type":"journal_article","isi":1,"scopus_import":"1","intvolume":" 20","date_updated":"2023-08-17T13:50:44Z","oa":1,"article_processing_charge":"No","title":"Are two given maps homotopic? An algorithmic viewpoint","publication":"Foundations of Computational Mathematics","language":[{"iso":"eng"}],"external_id":{"arxiv":["1312.2337"],"isi":["000522437400004"]},"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"}],"publication_status":"published","publisher":"Springer Nature","date_published":"2020-04-01T00:00:00Z","page":"311-330","department":[{"_id":"UlWa"}],"quality_controlled":"1","volume":20,"project":[{"grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF"}],"year":"2020","date_created":"2019-06-16T21:59:14Z","citation":{"ista":"Filakovský M, Vokřínek L. 2020. Are two given maps homotopic? An algorithmic viewpoint. Foundations of Computational Mathematics. 20, 311–330.","chicago":"Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An Algorithmic Viewpoint.” Foundations of Computational Mathematics. Springer Nature, 2020. https://doi.org/10.1007/s10208-019-09419-x.","mla":"Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An Algorithmic Viewpoint.” Foundations of Computational Mathematics, vol. 20, Springer Nature, 2020, pp. 311–30, doi:10.1007/s10208-019-09419-x.","ieee":"M. Filakovský and L. Vokřínek, “Are two given maps homotopic? An algorithmic viewpoint,” Foundations of Computational Mathematics, vol. 20. Springer Nature, pp. 311–330, 2020.","ama":"Filakovský M, Vokřínek L. Are two given maps homotopic? An algorithmic viewpoint. Foundations of Computational Mathematics. 2020;20:311-330. doi:10.1007/s10208-019-09419-x","short":"M. Filakovský, L. Vokřínek, Foundations of Computational Mathematics 20 (2020) 311–330.","apa":"Filakovský, M., & Vokřínek, L. (2020). Are two given maps homotopic? An algorithmic viewpoint. Foundations of Computational Mathematics. Springer Nature. https://doi.org/10.1007/s10208-019-09419-x"},"doi":"10.1007/s10208-019-09419-x","_id":"6563","article_type":"original"},{"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"}],"publication_status":"published","department":[{"_id":"UlWa"}],"quality_controlled":"1","volume":15,"publisher":"ACM","date_published":"2019-10-01T00:00:00Z","project":[{"call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"related_material":{"record":[{"id":"309","relation":"earlier_version","status":"public"}]},"article_number":"50","citation":{"ista":"Akitaya H, Fulek R, Tóth C. 2019. Recognizing weak embeddings of graphs. ACM Transactions on Algorithms. 15(4), 50.","chicago":"Akitaya, Hugo, Radoslav Fulek, and Csaba Tóth. “Recognizing Weak Embeddings of Graphs.” ACM Transactions on Algorithms. ACM, 2019. https://doi.org/10.1145/3344549.","mla":"Akitaya, Hugo, et al. “Recognizing Weak Embeddings of Graphs.” ACM Transactions on Algorithms, vol. 15, no. 4, 50, ACM, 2019, doi:10.1145/3344549.","ama":"Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. ACM Transactions on Algorithms. 2019;15(4). doi:10.1145/3344549","ieee":"H. Akitaya, R. Fulek, and C. Tóth, “Recognizing weak embeddings of graphs,” ACM Transactions on Algorithms, vol. 15, no. 4. ACM, 2019.","short":"H. Akitaya, R. Fulek, C. Tóth, ACM Transactions on Algorithms 15 (2019).","apa":"Akitaya, H., Fulek, R., & Tóth, C. (2019). Recognizing weak embeddings of graphs. ACM Transactions on Algorithms. ACM. https://doi.org/10.1145/3344549"},"date_created":"2019-11-04T15:45:17Z","year":"2019","doi":"10.1145/3344549","_id":"6982","article_type":"original","main_file_link":[{"url":"https://arxiv.org/abs/1709.09209","open_access":"1"}],"day":"01","oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"10","author":[{"last_name":"Akitaya","full_name":"Akitaya, Hugo","first_name":"Hugo"},{"full_name":"Fulek, Radoslav","first_name":"Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Tóth","full_name":"Tóth, Csaba","first_name":"Csaba"}],"arxiv":1,"type":"journal_article","status":"public","intvolume":" 15","scopus_import":1,"title":"Recognizing weak embeddings of graphs","oa":1,"date_updated":"2023-09-15T12:19:31Z","issue":"4","publication":"ACM Transactions on Algorithms","language":[{"iso":"eng"}]},{"type":"journal_article","status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1709.00508"}],"day":"29","oa_version":"Preprint","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_identifier":{"issn":["0209-9683"],"eissn":["1439-6912"]},"month":"10","author":[{"last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","first_name":"Radoslav"},{"last_name":"Kynčl","full_name":"Kynčl, Jan","first_name":"Jan"}],"arxiv":1,"publication":"Combinatorica","language":[{"iso":"eng"}],"scopus_import":"1","intvolume":" 39","isi":1,"title":"Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4","date_updated":"2023-08-30T07:26:25Z","oa":1,"article_processing_charge":"No","issue":"6","page":"1267-1279","department":[{"_id":"UlWa"}],"quality_controlled":"1","volume":39,"publisher":"Springer Nature","date_published":"2019-10-29T00:00:00Z","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"},{"_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF"}],"external_id":{"arxiv":["1709.00508"],"isi":["000493267200003"]},"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"}],"publication_status":"published","doi":"10.1007/s00493-019-3905-7","article_type":"original","_id":"7034","ec_funded":1,"citation":{"ieee":"R. Fulek and J. Kynčl, “Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4,” Combinatorica, vol. 39, no. 6. Springer Nature, pp. 1267–1279, 2019.","ama":"Fulek R, Kynčl J. Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4. Combinatorica. 2019;39(6):1267-1279. doi:10.1007/s00493-019-3905-7","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.","chicago":"Fulek, Radoslav, and Jan Kynčl. “Counterexample to an Extension of the Hanani-Tutte Theorem on the Surface of Genus 4.” Combinatorica. Springer Nature, 2019. https://doi.org/10.1007/s00493-019-3905-7.","mla":"Fulek, Radoslav, and Jan Kynčl. “Counterexample to an Extension of the Hanani-Tutte Theorem on the Surface of Genus 4.” Combinatorica, vol. 39, no. 6, Springer Nature, 2019, pp. 1267–79, doi:10.1007/s00493-019-3905-7.","apa":"Fulek, R., & Kynčl, J. (2019). Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-019-3905-7"},"date_created":"2019-11-18T14:29:50Z","year":"2019"},{"year":"2019","citation":{"apa":"Huszár, K., Spreer, J., & Wagner, U. (2019). On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. Computational Geometry Laborartoy. https://doi.org/10.20382/JOGC.V10I2A5","ieee":"K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,” Journal of Computational Geometry, 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. Journal of Computational Geometry. 2019;10(2):70–98. doi:10.20382/JOGC.V10I2A5","short":"K. Huszár, J. Spreer, U. Wagner, Journal of Computational Geometry 10 (2019) 70–98.","mla":"Huszár, Kristóf, et al. “On the Treewidth of Triangulated 3-Manifolds.” Journal of Computational Geometry, vol. 10, no. 2, Computational Geometry Laborartoy, 2019, pp. 70–98, doi:10.20382/JOGC.V10I2A5.","chicago":"Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds.” Journal of Computational Geometry. Computational Geometry Laborartoy, 2019. https://doi.org/10.20382/JOGC.V10I2A5.","ista":"Huszár K, Spreer J, Wagner U. 2019. On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. 10(2), 70–98."},"date_created":"2019-11-23T12:14:09Z","related_material":{"record":[{"id":"285","relation":"earlier_version","status":"public"},{"id":"8032","relation":"part_of_dissertation","status":"public"}]},"file_date_updated":"2020-07-14T12:47:49Z","_id":"7093","article_type":"original","doi":"10.20382/JOGC.V10I2A5","publication_status":"published","ddc":["514"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"external_id":{"arxiv":["1712.00434"]},"abstract":[{"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"}],"publisher":"Computational Geometry Laborartoy","date_published":"2019-11-01T00:00:00Z","department":[{"_id":"UlWa"}],"page":"70–98","volume":10,"quality_controlled":"1","oa":1,"date_updated":"2023-09-07T13:18:26Z","issue":"2","article_processing_charge":"No","title":"On the treewidth of triangulated 3-manifolds","intvolume":" 10","has_accepted_license":"1","language":[{"iso":"eng"}],"publication":"Journal of Computational Geometry","author":[{"first_name":"Kristóf","full_name":"Huszár, Kristóf","orcid":"0000-0002-5445-5057","id":"33C26278-F248-11E8-B48F-1D18A9856A87","last_name":"Huszár"},{"full_name":"Spreer, Jonathan","first_name":"Jonathan","last_name":"Spreer"},{"last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","full_name":"Wagner, Uli"}],"arxiv":1,"month":"11","publication_identifier":{"issn":["1920-180X"]},"day":"01","oa_version":"Published Version","file":[{"date_updated":"2020-07-14T12:47:49Z","date_created":"2019-11-23T12:35:16Z","file_id":"7094","file_name":"479-1917-1-PB.pdf","checksum":"c872d590d38d538404782bca20c4c3f5","file_size":857590,"content_type":"application/pdf","access_level":"open_access","relation":"main_file","creator":"khuszar"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","type":"journal_article"},{"department":[{"_id":"UlWa"}],"quality_controlled":"1","volume":66,"publisher":"ACM","date_published":"2019-06-01T00:00:00Z","external_id":{"isi":["000495406300007"],"arxiv":["1711.08436"]},"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."}],"publication_status":"published","doi":"10.1145/3314024","_id":"7108","article_type":"original","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"184"}]},"article_number":"21","date_created":"2019-11-26T10:13:59Z","citation":{"mla":"Goaoc, Xavier, et al. “Shellability Is NP-Complete.” Journal of the ACM, vol. 66, no. 3, 21, ACM, 2019, doi:10.1145/3314024.","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.” Journal of the ACM. ACM, 2019. https://doi.org/10.1145/3314024.","ama":"Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete. Journal of the ACM. 2019;66(3). doi:10.1145/3314024","ieee":"X. Goaoc, P. Patak, Z. Patakova, M. Tancer, and U. Wagner, “Shellability is NP-complete,” Journal of the ACM, vol. 66, no. 3. ACM, 2019.","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., & Wagner, U. (2019). Shellability is NP-complete. Journal of the ACM. ACM. https://doi.org/10.1145/3314024"},"year":"2019","status":"public","type":"journal_article","main_file_link":[{"open_access":"1","url":"https://arxiv.org/pdf/1711.08436.pdf"}],"oa_version":"Preprint","day":"01","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","month":"06","publication_identifier":{"issn":["0004-5411"]},"author":[{"last_name":"Goaoc","full_name":"Goaoc, Xavier","first_name":"Xavier"},{"full_name":"Patak, Pavel","first_name":"Pavel","last_name":"Patak","id":"B593B804-1035-11EA-B4F1-947645A5BB83"},{"full_name":"Patakova, Zuzana","first_name":"Zuzana","orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87","last_name":"Patakova"},{"first_name":"Martin","full_name":"Tancer, Martin","last_name":"Tancer"},{"first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"arxiv":1,"publication":"Journal of the ACM","language":[{"iso":"eng"}],"intvolume":" 66","scopus_import":"1","isi":1,"title":"Shellability is NP-complete","date_updated":"2023-09-06T11:10:58Z","oa":1,"issue":"3","article_processing_charge":"No"},{"project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"}],"page":"230-243","department":[{"_id":"UlWa"}],"quality_controlled":"1","volume":11904,"publisher":"Springer Nature","date_published":"2019-11-28T00:00:00Z","publication_status":"published","external_id":{"arxiv":["1908.08129"],"isi":["000612918800018"]},"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"}],"_id":"7230","doi":"10.1007/978-3-030-35802-0_18","date_created":"2020-01-05T23:00:47Z","citation":{"apa":"Arroyo Guevara, A. M., Derka, M., & Parada, I. (2019). Extending simple drawings. In 27th International Symposium on Graph Drawing and Network Visualization (Vol. 11904, pp. 230–243). Prague, Czech Republic: Springer Nature. https://doi.org/10.1007/978-3-030-35802-0_18","ieee":"A. M. Arroyo Guevara, M. Derka, and I. Parada, “Extending simple drawings,” in 27th International Symposium on Graph Drawing and Network Visualization, Prague, Czech Republic, 2019, vol. 11904, pp. 230–243.","ama":"Arroyo Guevara AM, Derka M, Parada I. Extending simple drawings. In: 27th International Symposium on Graph Drawing and Network Visualization. Vol 11904. Springer Nature; 2019:230-243. doi:10.1007/978-3-030-35802-0_18","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.","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.","mla":"Arroyo Guevara, Alan M., et al. “Extending Simple Drawings.” 27th International Symposium on Graph Drawing and Network Visualization, vol. 11904, Springer Nature, 2019, pp. 230–43, doi:10.1007/978-3-030-35802-0_18.","chicago":"Arroyo Guevara, Alan M, Martin Derka, and Irene Parada. “Extending Simple Drawings.” In 27th International Symposium on Graph Drawing and Network Visualization, 11904:230–43. Springer Nature, 2019. https://doi.org/10.1007/978-3-030-35802-0_18."},"year":"2019","ec_funded":1,"alternative_title":["LNCS"],"type":"conference","status":"public","author":[{"orcid":"0000-0003-2401-8670","last_name":"Arroyo Guevara","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","first_name":"Alan M","full_name":"Arroyo Guevara, Alan M"},{"full_name":"Derka, Martin","first_name":"Martin","last_name":"Derka"},{"last_name":"Parada","first_name":"Irene","full_name":"Parada, Irene"}],"arxiv":1,"day":"28","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1908.08129"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","conference":{"start_date":"2019-09-17","name":"GD: Graph Drawing and Network Visualization","end_date":"2019-09-20","location":"Prague, Czech Republic"},"month":"11","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["978-3-0303-5801-3"]},"language":[{"iso":"eng"}],"publication":"27th International Symposium on Graph Drawing and Network Visualization","title":"Extending simple drawings","date_updated":"2023-09-06T14:56:00Z","oa":1,"article_processing_charge":"No","intvolume":" 11904","scopus_import":"1","isi":1},{"article_number":"39","date_created":"2020-01-29T16:17:05Z","citation":{"apa":"Fulek, R., & Kyncl, J. (2019). Z_2-Genus of graphs and minimum rank of partial symmetric matrices. In 35th International Symposium on Computational Geometry (SoCG 2019) (Vol. 129). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.39","mla":"Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices.” 35th International Symposium on Computational Geometry (SoCG 2019), vol. 129, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.SOCG.2019.39.","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.","chicago":"Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices.” In 35th International Symposium on Computational Geometry (SoCG 2019), Vol. 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.SOCG.2019.39.","short":"R. Fulek, J. Kyncl, in:, 35th International Symposium on Computational Geometry (SoCG 2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.","ieee":"R. Fulek and J. Kyncl, “Z_2-Genus of graphs and minimum rank of partial symmetric matrices,” in 35th International Symposium on Computational Geometry (SoCG 2019), Portland, OR, United States, 2019, vol. 129.","ama":"Fulek R, Kyncl J. Z_2-Genus of graphs and minimum rank of partial symmetric matrices. In: 35th International Symposium on Computational Geometry (SoCG 2019). Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.SOCG.2019.39"},"year":"2019","doi":"10.4230/LIPICS.SOCG.2019.39","_id":"7401","file_date_updated":"2020-07-14T12:47:57Z","abstract":[{"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. ","lang":"eng"}],"external_id":{"arxiv":["1903.08637"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["000"],"publication_status":"published","volume":129,"quality_controlled":"1","department":[{"_id":"UlWa"}],"date_published":"2019-06-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281"}],"scopus_import":1,"has_accepted_license":"1","intvolume":" 129","title":"Z_2-Genus of graphs and minimum rank of partial symmetric matrices","article_processing_charge":"No","oa":1,"date_updated":"2021-01-12T08:13:24Z","publication":"35th International Symposium on Computational Geometry (SoCG 2019)","language":[{"iso":"eng"}],"file":[{"creator":"dernst","file_size":628347,"content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_name":"2019_LIPIcs_Fulek.pdf","checksum":"aac37b09118cc0ab58cf77129e691f8c","file_id":"7445","date_created":"2020-02-04T09:14:31Z","date_updated":"2020-07-14T12:47:57Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","oa_version":"Published Version","publication_identifier":{"isbn":["978-3-95977-104-7"],"issn":["1868-8969"]},"month":"06","conference":{"location":"Portland, OR, United States","end_date":"2019-06-21","name":"SoCG: Symposium on Computational Geometry","start_date":"2019-06-18"},"arxiv":1,"author":[{"full_name":"Fulek, Radoslav","first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774"},{"first_name":"Jan","full_name":"Kyncl, Jan","last_name":"Kyncl"}],"status":"public","type":"conference","alternative_title":["LIPIcs"]},{"article_number":"1903.06981","related_material":{"record":[{"relation":"dissertation_contains","id":"7944","status":"public"},{"relation":"later_version","id":"12833","status":"public"}]},"citation":{"ieee":"A. Biniaz et al., “Token swapping on trees,” arXiv. .","ama":"Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. arXiv.","short":"A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec, A. Turcotte, ArXiv (n.d.).","mla":"Biniaz, Ahmad, et al. “Token Swapping on Trees.” ArXiv, 1903.06981.","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.","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.” ArXiv, n.d.","apa":"Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte, A. (n.d.). Token swapping on trees. arXiv."},"date_created":"2020-06-08T12:25:25Z","title":"Token swapping on trees","date_updated":"2024-01-04T12:42:08Z","oa":1,"article_processing_charge":"No","year":"2019","publication":"arXiv","language":[{"iso":"eng"}],"_id":"7950","day":"16","external_id":{"arxiv":["1903.06981"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1903.06981"}],"oa_version":"Preprint","abstract":[{"lang":"eng","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."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"03","author":[{"first_name":"Ahmad","full_name":"Biniaz, Ahmad","last_name":"Biniaz"},{"last_name":"Jain","first_name":"Kshitij","full_name":"Jain, Kshitij"},{"full_name":"Lubiw, Anna","first_name":"Anna","last_name":"Lubiw"},{"orcid":"0000-0002-6660-1322","last_name":"Masárová","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","full_name":"Masárová, Zuzana"},{"last_name":"Miltzow","full_name":"Miltzow, Tillmann","first_name":"Tillmann"},{"first_name":"Debajyoti","full_name":"Mondal, Debajyoti","last_name":"Mondal"},{"last_name":"Naredla","full_name":"Naredla, Anurag Murty","first_name":"Anurag Murty"},{"full_name":"Tkadlec, Josef","first_name":"Josef","orcid":"0000-0002-1097-9684","last_name":"Tkadlec","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Turcotte, Alexi","first_name":"Alexi","last_name":"Turcotte"}],"publication_status":"submitted","arxiv":1,"department":[{"_id":"HeEd"},{"_id":"UlWa"},{"_id":"KrCh"}],"status":"public","date_published":"2019-03-16T00:00:00Z","type":"preprint"},{"status":"public","date_published":"2019-10-28T00:00:00Z","type":"preprint","publisher":"arXiv","department":[{"_id":"UlWa"}],"project":[{"name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF","grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425"}],"month":"10","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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."}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1910.12628"}],"oa_version":"Preprint","day":"28","external_id":{"arxiv":["1910.12628"]},"arxiv":1,"publication_status":"submitted","author":[{"first_name":"Sergey","full_name":"Avvakumov, Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","last_name":"Avvakumov"},{"full_name":"Kudrya, Sergey","first_name":"Sergey","id":"ecf01965-d252-11ea-95a5-8ada5f6c6a67","last_name":"Kudrya"}],"publication":"arXiv","language":[{"iso":"eng"}],"_id":"8182","related_material":{"record":[{"status":"public","id":"11446","relation":"later_version"},{"relation":"dissertation_contains","id":"8156","status":"public"}]},"article_number":"1910.12628","article_processing_charge":"No","year":"2019","date_updated":"2023-09-07T13:12:17Z","oa":1,"date_created":"2020-07-30T10:45:08Z","citation":{"ista":"Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping degree. arXiv, 1910.12628.","mla":"Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions and the Mapping Degree.” ArXiv, 1910.12628, arXiv.","chicago":"Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions and the Mapping Degree.” ArXiv. arXiv, n.d.","short":"S. Avvakumov, S. Kudrya, ArXiv (n.d.).","ama":"Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping degree. arXiv.","ieee":"S. Avvakumov and S. Kudrya, “Vanishing of all equivariant obstructions and the mapping degree,” arXiv. arXiv.","apa":"Avvakumov, S., & Kudrya, S. (n.d.). Vanishing of all equivariant obstructions and the mapping degree. arXiv. arXiv."},"title":"Vanishing of all equivariant obstructions and the mapping degree"},{"oa":1,"acknowledgement":"We would like to thank F. Frick for helpful discussions","date_updated":"2023-09-08T11:20:02Z","year":"2019","article_processing_charge":"No","title":"Stronger counterexamples to the topological Tverberg conjecture","date_created":"2020-07-30T10:45:34Z","citation":{"ieee":"S. Avvakumov, R. Karasev, and A. Skopenkov, “Stronger counterexamples to the topological Tverberg conjecture,” arXiv. arXiv.","ama":"Avvakumov S, Karasev R, Skopenkov A. Stronger counterexamples to the topological Tverberg conjecture. arXiv.","short":"S. Avvakumov, R. Karasev, A. Skopenkov, ArXiv (n.d.).","chicago":"Avvakumov, Sergey, R. Karasev, and A. Skopenkov. “Stronger Counterexamples to the Topological Tverberg Conjecture.” ArXiv. arXiv, n.d.","mla":"Avvakumov, Sergey, et al. “Stronger Counterexamples to the Topological Tverberg Conjecture.” ArXiv, 1908.08731, arXiv.","ista":"Avvakumov S, Karasev R, Skopenkov A. Stronger counterexamples to the topological Tverberg conjecture. arXiv, 1908.08731.","apa":"Avvakumov, S., Karasev, R., & Skopenkov, A. (n.d.). Stronger counterexamples to the topological Tverberg conjecture. arXiv. arXiv."},"isi":1,"related_material":{"record":[{"relation":"dissertation_contains","id":"8156","status":"public"}]},"article_number":"1908.08731","language":[{"iso":"eng"}],"_id":"8184","publication":"arXiv","publication_status":"submitted","author":[{"full_name":"Avvakumov, Sergey","first_name":"Sergey","last_name":"Avvakumov","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"R.","full_name":"Karasev, R.","last_name":"Karasev"},{"full_name":"Skopenkov, A.","first_name":"A.","last_name":"Skopenkov"}],"arxiv":1,"month":"08","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1908.08731"}],"oa_version":"Preprint","day":"23","external_id":{"arxiv":["1908.08731"],"isi":["000986519600004"]},"abstract":[{"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. ","lang":"eng"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","grant_number":"P31312"}],"publisher":"arXiv","type":"preprint","status":"public","date_published":"2019-08-23T00:00:00Z","department":[{"_id":"UlWa"}]},{"publication_status":"submitted","author":[{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","last_name":"Avvakumov","first_name":"Sergey","full_name":"Avvakumov, Sergey"},{"last_name":"Karasev","full_name":"Karasev, Roman","first_name":"Roman"}],"arxiv":1,"main_file_link":[{"url":"https://arxiv.org/abs/1907.11183","open_access":"1"}],"day":"25","oa_version":"Preprint","external_id":{"arxiv":["1907.11183"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","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."}],"month":"07","project":[{"_id":"26611F5C-B435-11E9-9278-68D0E5697425","grant_number":"P31312","name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF"}],"department":[{"_id":"UlWa"}],"status":"public","type":"preprint","date_published":"2019-07-25T00:00:00Z","citation":{"apa":"Avvakumov, S., & Karasev, R. (n.d.). Envy-free division using mapping degree. arXiv. https://doi.org/10.48550/arXiv.1907.11183","short":"S. Avvakumov, R. Karasev, ArXiv (n.d.).","ama":"Avvakumov S, Karasev R. Envy-free division using mapping degree. arXiv. doi:10.48550/arXiv.1907.11183","ieee":"S. Avvakumov and R. Karasev, “Envy-free division using mapping degree,” arXiv. .","mla":"Avvakumov, Sergey, and Roman Karasev. “Envy-Free Division Using Mapping Degree.” ArXiv, 1907.11183, doi:10.48550/arXiv.1907.11183.","ista":"Avvakumov S, Karasev R. Envy-free division using mapping degree. arXiv, 1907.11183.","chicago":"Avvakumov, Sergey, and Roman Karasev. “Envy-Free Division Using Mapping Degree.” ArXiv, n.d. https://doi.org/10.48550/arXiv.1907.11183."},"title":"Envy-free division using mapping degree","date_created":"2020-07-30T10:45:51Z","date_updated":"2023-09-07T13:12:17Z","oa":1,"year":"2019","article_processing_charge":"No","related_material":{"link":[{"relation":"later_version","url":"https://doi.org/10.1112/mtk.12059"}],"record":[{"relation":"dissertation_contains","id":"8156","status":"public"}]},"article_number":"1907.11183","language":[{"iso":"eng"}],"_id":"8185","doi":"10.48550/arXiv.1907.11183","publication":"arXiv"}]