[{"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"}],"type":"conference","alternative_title":["LIPIcs"],"file":[{"file_size":592661,"content_type":"application/pdf","creator":"dernst","file_name":"2020_LIPIcsSoCG_Arroyo.pdf","access_level":"open_access","date_created":"2020-06-23T11:06:23Z","date_updated":"2020-07-14T12:48:06Z","checksum":"93571b76cf97d5b7c8aabaeaa694dd7e","relation":"main_file","file_id":"8006"}],"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"7994","title":"Extending drawings of graphs to arrangements of pseudolines","status":"public","ddc":["510"],"intvolume":" 164","day":"01","article_processing_charge":"No","has_accepted_license":"1","scopus_import":"1","date_published":"2020-06-01T00:00:00Z","publication":"36th International Symposium on Computational Geometry","citation":{"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.","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","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.","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","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.","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."},"file_date_updated":"2020-07-14T12:48:06Z","ec_funded":1,"article_number":"9:1 - 9:14","author":[{"full_name":"Arroyo Guevara, Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2401-8670","first_name":"Alan M","last_name":"Arroyo Guevara"},{"full_name":"Bensmail, Julien","last_name":"Bensmail","first_name":"Julien"},{"last_name":"Bruce Richter","first_name":"R.","full_name":"Bruce Richter, R."}],"date_updated":"2023-02-23T13:22:12Z","date_created":"2020-06-22T09:14:21Z","volume":164,"year":"2020","publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"month":"06","publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"conference":{"start_date":"2020-06-22","location":"Zürich, Switzerland","end_date":"2020-06-26","name":"SoCG: Symposium on Computational Geometry"},"doi":"10.4230/LIPIcs.SoCG.2020.9","language":[{"iso":"eng"}],"oa":1,"tmp":{"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)","image":"/images/cc_by.png"},"external_id":{"arxiv":["1804.09317"]},"quality_controlled":"1","project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"}]},{"file_date_updated":"2020-07-14T12:48:06Z","article_number":"67:1 - 67:16","date_updated":"2023-08-04T08:51:07Z","date_created":"2020-06-22T09:14:19Z","volume":164,"author":[{"last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"},{"first_name":"Emo","last_name":"Welzl","full_name":"Welzl, Emo"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"12129"}]},"publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2020","month":"06","publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"language":[{"iso":"eng"}],"conference":{"start_date":"2020-06-22","location":"Zürich, Switzerland","end_date":"2020-06-26","name":"SoCG: Symposium on Computational Geometry"},"doi":"10.4230/LIPIcs.SoCG.2020.67","quality_controlled":"1","tmp":{"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)","image":"/images/cc_by.png"},"external_id":{"arxiv":["2003.13557"]},"oa":1,"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)."}],"alternative_title":["LIPIcs"],"type":"conference","file":[{"content_type":"application/pdf","file_size":793187,"creator":"dernst","access_level":"open_access","file_name":"2020_LIPIcsSoCG_Wagner.pdf","checksum":"3f6925be5f3dcdb3b14cab92f410edf7","date_updated":"2020-07-14T12:48:06Z","date_created":"2020-06-23T06:37:27Z","relation":"main_file","file_id":"8003"}],"oa_version":"Published Version","ddc":["510"],"title":"Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips)","status":"public","intvolume":" 164","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"7990","day":"01","article_processing_charge":"No","has_accepted_license":"1","scopus_import":1,"date_published":"2020-06-01T00:00:00Z","publication":"36th International Symposium on Computational Geometry","citation":{"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.","short":"U. Wagner, E. Welzl, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","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.","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.","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","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."}},{"main_file_link":[{"url":"https://doi.org/10.1137/1.9781611975994.172","open_access":"1"}],"external_id":{"arxiv":["2003.13557"]},"oa":1,"quality_controlled":"1","doi":"10.1137/1.9781611975994.172","conference":{"start_date":"2020-01-05","location":"Salt Lake City, UT, United States","end_date":"2020-01-08","name":"SODA: Symposium on Discrete Algorithms"},"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9781611975994"]},"month":"01","year":"2020","publisher":"SIAM","department":[{"_id":"UlWa"}],"publication_status":"published","related_material":{"record":[{"id":"12129","relation":"later_version","status":"public"}]},"author":[{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"},{"first_name":"Emo","last_name":"Welzl","full_name":"Welzl, Emo"}],"volume":"2020-January","date_created":"2020-05-10T22:00:48Z","date_updated":"2023-08-04T08:51:07Z","citation":{"short":"U. Wagner, E. Welzl, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 2823–2841.","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips).” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 2020–January, SIAM, 2020, pp. 2823–41, doi:10.1137/1.9781611975994.172.","chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips).” In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2020–January:2823–41. SIAM, 2020. https://doi.org/10.1137/1.9781611975994.172.","ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 2020-January. SIAM; 2020:2823-2841. doi:10.1137/1.9781611975994.172","apa":"Wagner, U., & Welzl, E. (2020). Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 2020–January, pp. 2823–2841). Salt Lake City, UT, United States: SIAM. https://doi.org/10.1137/1.9781611975994.172","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane (Part I: Edge flips),” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, UT, United States, 2020, vol. 2020–January, pp. 2823–2841.","ista":"Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2020–January, 2823–2841."},"publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","page":"2823-2841","date_published":"2020-01-01T00:00:00Z","scopus_import":1,"article_processing_charge":"No","day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"7807","status":"public","title":"Connectivity of triangulation flip graphs in the plane (Part I: Edge flips)","oa_version":"Submitted Version","type":"conference","abstract":[{"text":"In a straight-line embedded triangulation of a point set P in the plane, removing an inner edge and—provided the resulting quadrilateral is convex—adding the other diagonal is called an edge flip. The (edge) flip graph has all triangulations as vertices, and a pair of triangulations is adjacent if they can be obtained from each other by an edge flip. The goal of this paper is to contribute to a better understanding of the flip graph, with an emphasis on its connectivity.\r\nFor sets in general position, it is known that every triangulation allows at least edge flips (a tight bound) which gives the minimum degree of any flip graph for n points. We show that for every point set P in general position, the flip graph is at least -vertex connected. Somewhat more strongly, we show that the vertex connectivity equals the minimum degree occurring in the flip graph, i.e. the minimum number of flippable edges in any triangulation of P, provided P is large enough. Finally, we exhibit some of the geometry of the flip graph by showing that the flip graph can be covered by 1-skeletons of polytopes of dimension (products of associahedra).\r\nA corresponding result ((n – 3)-vertex connectedness) can be shown for the bistellar flip graph of partial triangulations, i.e. the set of all triangulations of subsets of P which contain all extreme points of P. This will be treated separately in a second part.","lang":"eng"}]},{"author":[{"first_name":"Sergey","last_name":"Avvakumov","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","full_name":"Avvakumov, Sergey"},{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"},{"last_name":"Mabillard","first_name":"Isaac","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","full_name":"Mabillard, Isaac"},{"full_name":"Skopenkov, A. B.","first_name":"A. B.","last_name":"Skopenkov"}],"related_material":{"record":[{"id":"8183","relation":"earlier_version","status":"public"},{"id":"10220","relation":"later_version","status":"public"}]},"date_created":"2021-04-04T22:01:22Z","date_updated":"2023-08-14T11:43:54Z","volume":75,"acknowledgement":"This research was carried out with the support of the Russian Foundation for Basic Research(grant no. 19-01-00169)","year":"2020","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"IOP Publishing","doi":"10.1070/RM9943","language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1511.03501","open_access":"1"}],"external_id":{"isi":["000625983100001"],"arxiv":["1511.03501"]},"isi":1,"quality_controlled":"1","month":"12","publication_identifier":{"issn":["0036-0279"]},"oa_version":"Preprint","_id":"9308","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public","title":"Eliminating higher-multiplicity intersections, III. Codimension 2","intvolume":" 75","issue":"6","type":"journal_article","date_published":"2020-12-01T00:00:00Z","publication":"Russian Mathematical Surveys","citation":{"chicago":"Avvakumov, Sergey, Uli Wagner, Isaac Mabillard, and A. B. Skopenkov. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” Russian Mathematical Surveys. IOP Publishing, 2020. https://doi.org/10.1070/RM9943.","short":"S. Avvakumov, U. Wagner, I. Mabillard, A.B. Skopenkov, Russian Mathematical Surveys 75 (2020) 1156–1158.","mla":"Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” Russian Mathematical Surveys, vol. 75, no. 6, IOP Publishing, 2020, pp. 1156–58, doi:10.1070/RM9943.","apa":"Avvakumov, S., Wagner, U., Mabillard, I., & Skopenkov, A. B. (2020). Eliminating higher-multiplicity intersections, III. Codimension 2. Russian Mathematical Surveys. IOP Publishing. https://doi.org/10.1070/RM9943","ieee":"S. Avvakumov, U. Wagner, I. Mabillard, and A. B. Skopenkov, “Eliminating higher-multiplicity intersections, III. Codimension 2,” Russian Mathematical Surveys, vol. 75, no. 6. IOP Publishing, pp. 1156–1158, 2020.","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. Russian Mathematical Surveys. 2020;75(6):1156-1158. doi:10.1070/RM9943"},"article_type":"original","page":"1156-1158","day":"01","article_processing_charge":"No","scopus_import":"1"},{"month":"04","publication_identifier":{"issn":["16153375"],"eissn":["16153383"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1312.2337"}],"external_id":{"isi":["000522437400004"],"arxiv":["1312.2337"]},"isi":1,"quality_controlled":"1","project":[{"_id":"26611F5C-B435-11E9-9278-68D0E5697425","grant_number":"P31312","name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF"}],"doi":"10.1007/s10208-019-09419-x","language":[{"iso":"eng"}],"year":"2020","publication_status":"published","publisher":"Springer Nature","department":[{"_id":"UlWa"}],"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"}],"date_created":"2019-06-16T21:59:14Z","date_updated":"2023-08-17T13:50:44Z","volume":20,"scopus_import":"1","day":"01","article_processing_charge":"No","publication":"Foundations of Computational Mathematics","citation":{"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.","short":"M. Filakovský, L. Vokřínek, Foundations of Computational Mathematics 20 (2020) 311–330.","ista":"Filakovský M, Vokřínek L. 2020. Are two given maps homotopic? An algorithmic viewpoint. Foundations of Computational Mathematics. 20, 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","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"},"article_type":"original","page":"311-330","date_published":"2020-04-01T00:00:00Z","type":"journal_article","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"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"6563","title":"Are two given maps homotopic? An algorithmic viewpoint","status":"public","intvolume":" 20","oa_version":"Preprint"},{"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"}],"type":"journal_article","oa_version":"Preprint","intvolume":" 64","status":"public","title":"Intersection patterns of planar sets","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"7960","article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2020-09-01T00:00:00Z","page":"304-323","article_type":"original","citation":{"ista":"Kalai G, Patakova Z. 2020. Intersection patterns of planar sets. Discrete and Computational Geometry. 64, 304–323.","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","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","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.","short":"G. Kalai, Z. Patakova, Discrete and Computational Geometry 64 (2020) 304–323."},"publication":"Discrete and Computational Geometry","volume":64,"date_updated":"2023-08-21T08:26:34Z","date_created":"2020-06-14T22:00:50Z","author":[{"full_name":"Kalai, Gil","last_name":"Kalai","first_name":"Gil"},{"id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683","first_name":"Zuzana","last_name":"Patakova","full_name":"Patakova, Zuzana"}],"publisher":"Springer Nature","department":[{"_id":"UlWa"}],"publication_status":"published","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","publication_identifier":{"eissn":["14320444"],"issn":["01795376"]},"month":"09","language":[{"iso":"eng"}],"doi":"10.1007/s00454-020-00205-z","isi":1,"quality_controlled":"1","oa":1,"external_id":{"isi":["000537329400001"],"arxiv":["1907.00885"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1907.00885"}]},{"article_processing_charge":"No","day":"09","scopus_import":"1","date_published":"2020-10-09T00:00:00Z","page":"325-338","citation":{"mla":"Arroyo Guevara, Alan M., et al. “Inserting One Edge into a Simple Drawing Is Hard.” Graph-Theoretic Concepts in Computer Science, vol. 12301, Springer Nature, 2020, pp. 325–38, doi:10.1007/978-3-030-60440-0_26.","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.","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 Graph-Theoretic Concepts in Computer Science, 12301:325–38. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-60440-0_26.","ama":"Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T. Inserting one edge into a simple drawing is hard. In: Graph-Theoretic Concepts in Computer Science. Vol 12301. Springer Nature; 2020:325-338. doi:10.1007/978-3-030-60440-0_26","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.","apa":"Arroyo Guevara, A. M., Klute, F., Parada, I., Seidel, R., Vogtenhuber, B., & Wiedera, T. (2020). Inserting one edge into a simple drawing is hard. In Graph-Theoretic Concepts in Computer Science (Vol. 12301, pp. 325–338). Leeds, United Kingdom: Springer Nature. https://doi.org/10.1007/978-3-030-60440-0_26","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 Graph-Theoretic Concepts in Computer Science, Leeds, United Kingdom, 2020, vol. 12301, pp. 325–338."},"publication":"Graph-Theoretic Concepts in Computer Science","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."}],"alternative_title":["LNCS"],"type":"conference","oa_version":"None","intvolume":" 12301","title":"Inserting one edge into a simple drawing is hard","status":"public","_id":"8732","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783030604394","9783030604400"],"issn":["0302-9743"]},"month":"10","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-60440-0_26","conference":{"end_date":"2020-06-26","location":"Leeds, United Kingdom","start_date":"2020-06-24","name":"WG: Workshop on Graph-Theoretic Concepts in Computer Science"},"project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}],"quality_controlled":"1","ec_funded":1,"volume":12301,"date_created":"2020-11-06T08:45:03Z","date_updated":"2023-09-05T15:09:16Z","author":[{"full_name":"Arroyo Guevara, Alan M","orcid":"0000-0003-2401-8670","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","last_name":"Arroyo Guevara","first_name":"Alan M"},{"full_name":"Klute, Fabian","first_name":"Fabian","last_name":"Klute"},{"last_name":"Parada","first_name":"Irene","full_name":"Parada, Irene"},{"last_name":"Seidel","first_name":"Raimund","full_name":"Seidel, Raimund"},{"full_name":"Vogtenhuber, Birgit","last_name":"Vogtenhuber","first_name":"Birgit"},{"full_name":"Wiedera, Tilo","last_name":"Wiedera","first_name":"Tilo"}],"department":[{"_id":"UlWa"}],"publisher":"Springer Nature","publication_status":"published","year":"2020"},{"abstract":[{"text":"This thesis considers two examples of reconfiguration problems: flipping edges in edge-labelled triangulations of planar point sets and swapping labelled tokens placed on vertices of a graph. In both cases the studied structures – all the triangulations of a given point set or all token placements on a given graph – can be thought of as vertices of the so-called reconfiguration graph, in which two vertices are adjacent if the corresponding structures differ by a single elementary operation – by a flip of a diagonal in a triangulation or by a swap of tokens on adjacent vertices, respectively. We study the reconfiguration of one instance of a structure into another via (shortest) paths in the reconfiguration graph.\r\n\r\nFor triangulations of point sets in which each edge has a unique label and a flip transfers the label from the removed edge to the new edge, we prove a polynomial-time testable condition, called the Orbit Theorem, that characterizes when two triangulations of the same point set lie in the same connected component of the reconfiguration graph. The condition was first conjectured by Bose, Lubiw, Pathak and Verdonschot. We additionally provide a polynomial time algorithm that computes a reconfiguring flip sequence, if it exists. Our proof of the Orbit Theorem uses topological properties of a certain high-dimensional cell complex that has the usual reconfiguration graph as its 1-skeleton.\r\n\r\nIn the context of token swapping on a tree graph, we make partial progress on the problem of finding shortest reconfiguration sequences. We disprove the so-called Happy Leaf Conjecture and demonstrate the importance of swapping tokens that are already placed at the correct vertices. We also prove that a generalization of the problem to weighted coloured token swapping is NP-hard on trees but solvable in polynomial time on paths and stars.","lang":"eng"}],"type":"dissertation","alternative_title":["ISTA Thesis"],"file":[{"file_id":"7945","relation":"main_file","date_updated":"2020-07-14T12:48:05Z","date_created":"2020-06-08T00:34:00Z","checksum":"df688bc5a82b50baee0b99d25fc7b7f0","file_name":"THESIS_Zuzka_Masarova.pdf","access_level":"open_access","creator":"zmasarov","content_type":"application/pdf","file_size":13661779},{"date_updated":"2020-07-14T12:48:05Z","date_created":"2020-06-08T00:35:30Z","checksum":"45341a35b8f5529c74010b7af43ac188","relation":"source_file","file_id":"7946","file_size":32184006,"content_type":"application/zip","creator":"zmasarov","file_name":"THESIS_Zuzka_Masarova_SOURCE_FILES.zip","access_level":"closed"}],"oa_version":"Published Version","_id":"7944","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","title":"Reconfiguration problems","ddc":["516","514"],"has_accepted_license":"1","article_processing_charge":"No","day":"09","keyword":["reconfiguration","reconfiguration graph","triangulations","flip","constrained triangulations","shellability","piecewise-linear balls","token swapping","trees","coloured weighted token swapping"],"date_published":"2020-06-09T00:00:00Z","citation":{"chicago":"Masárová, Zuzana. “Reconfiguration Problems.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7944.","short":"Z. Masárová, Reconfiguration Problems, Institute of Science and Technology Austria, 2020.","mla":"Masárová, Zuzana. Reconfiguration Problems. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7944.","ieee":"Z. Masárová, “Reconfiguration problems,” Institute of Science and Technology Austria, 2020.","apa":"Masárová, Z. (2020). Reconfiguration problems. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:7944","ista":"Masárová Z. 2020. Reconfiguration problems. Institute of Science and Technology Austria.","ama":"Masárová Z. Reconfiguration problems. 2020. doi:10.15479/AT:ISTA:7944"},"page":"160","file_date_updated":"2020-07-14T12:48:05Z","license":"https://creativecommons.org/licenses/by-sa/4.0/","related_material":{"record":[{"relation":"part_of_dissertation","status":"public","id":"7950"},{"status":"public","relation":"part_of_dissertation","id":"5986"}]},"author":[{"full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322","first_name":"Zuzana","last_name":"Masárová"}],"date_created":"2020-06-08T00:49:46Z","date_updated":"2023-09-07T13:17:37Z","year":"2020","department":[{"_id":"HeEd"},{"_id":"UlWa"}],"publisher":"Institute of Science and Technology Austria","publication_status":"published","publication_identifier":{"issn":["2663-337X"],"isbn":["978-3-99078-005-3"]},"month":"06","doi":"10.15479/AT:ISTA:7944","language":[{"iso":"eng"}],"supervisor":[{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"},{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"}],"degree_awarded":"PhD","tmp":{"short":"CC BY-SA (4.0)","image":"/images/cc_by_sa.png","name":"Creative Commons Attribution-ShareAlike 4.0 International Public License (CC BY-SA 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-sa/4.0/legalcode"},"oa":1},{"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."}],"type":"dissertation","alternative_title":["ISTA Thesis"],"oa_version":"Published Version","file":[{"checksum":"bd8be6e4f1addc863dfcc0fad29ee9c3","date_updated":"2020-07-14T12:48:08Z","date_created":"2020-06-26T10:03:58Z","file_id":"8034","relation":"main_file","creator":"khuszar","file_size":2637562,"content_type":"application/pdf","access_level":"open_access","file_name":"Kristof_Huszar-Thesis.pdf"},{"file_id":"8035","relation":"source_file","checksum":"d5f8456202b32f4a77552ef47a2837d1","date_updated":"2020-07-14T12:48:08Z","date_created":"2020-06-26T10:10:06Z","access_level":"closed","file_name":"Kristof_Huszar-Thesis-source.zip","creator":"khuszar","file_size":7163491,"content_type":"application/x-zip-compressed"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"8032","status":"public","title":"Combinatorial width parameters for 3-dimensional manifolds","ddc":["514"],"day":"26","has_accepted_license":"1","article_processing_charge":"No","date_published":"2020-06-26T00:00:00Z","citation":{"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.","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.","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.","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","ieee":"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"},"page":"xviii+120","file_date_updated":"2020-07-14T12:48:08Z","author":[{"full_name":"Huszár, Kristóf","id":"33C26278-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5445-5057","first_name":"Kristóf","last_name":"Huszár"}],"related_material":{"record":[{"id":"6556","relation":"dissertation_contains","status":"public"},{"relation":"dissertation_contains","status":"public","id":"7093"}]},"date_updated":"2023-09-07T13:18:27Z","date_created":"2020-06-26T10:00:36Z","year":"2020","publication_status":"published","publisher":"Institute of Science and Technology Austria","department":[{"_id":"UlWa"}],"month":"06","publication_identifier":{"isbn":["978-3-99078-006-0"],"issn":["2663-337X"]},"doi":"10.15479/AT:ISTA:8032","acknowledged_ssus":[{"_id":"E-Lib"},{"_id":"CampIT"}],"degree_awarded":"PhD","supervisor":[{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner","full_name":"Wagner, Uli"},{"full_name":"Spreer, Jonathan","first_name":"Jonathan","last_name":"Spreer"}],"language":[{"iso":"eng"}],"tmp":{"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)","image":"/images/cc_by.png"},"oa":1},{"oa":1,"doi":"10.15479/AT:ISTA:8156","language":[{"iso":"eng"}],"degree_awarded":"PhD","supervisor":[{"full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"publication_identifier":{"issn":["2663-337X"]},"month":"07","year":"2020","department":[{"_id":"UlWa"}],"publisher":"Institute of Science and Technology Austria","publication_status":"published","related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"8182"},{"id":"8183","relation":"part_of_dissertation","status":"public"},{"status":"public","relation":"part_of_dissertation","id":"8185"},{"id":"8184","status":"public","relation":"part_of_dissertation"},{"id":"6355","status":"public","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","status":"public","id":"75"}]},"author":[{"full_name":"Avvakumov, Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey","last_name":"Avvakumov"}],"date_created":"2020-07-23T09:51:29Z","date_updated":"2023-12-18T10:51:01Z","file_date_updated":"2020-07-27T12:46:53Z","citation":{"mla":"Avvakumov, Sergey. Topological Methods in Geometry and Discrete Mathematics. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:8156.","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. https://doi.org/10.15479/AT:ISTA:8156.","ama":"Avvakumov S. Topological methods in geometry and discrete mathematics. 2020. doi:10.15479/AT:ISTA:8156","ista":"Avvakumov S. 2020. Topological methods in geometry and discrete mathematics. Institute of Science and Technology Austria.","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","ieee":"S. Avvakumov, “Topological methods in geometry and discrete mathematics,” Institute of Science and Technology Austria, 2020."},"page":"119","date_published":"2020-07-24T00:00:00Z","article_processing_charge":"No","has_accepted_license":"1","day":"24","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"8156","status":"public","title":"Topological methods in geometry and discrete mathematics","ddc":["514"],"file":[{"content_type":"application/zip","file_size":1061740,"creator":"savvakum","access_level":"closed","file_name":"source.zip","date_updated":"2020-07-27T12:44:51Z","date_created":"2020-07-27T12:44:51Z","relation":"source_file","file_id":"8178"},{"file_name":"thesis_pdfa.pdf","access_level":"open_access","creator":"savvakum","content_type":"application/pdf","file_size":1336501,"file_id":"8179","relation":"main_file","date_updated":"2020-07-27T12:46:53Z","date_created":"2020-07-27T12:46:53Z","success":1}],"oa_version":"Published Version","type":"dissertation","alternative_title":["ISTA Thesis"],"abstract":[{"lang":"eng","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."}]},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"15082","year":"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.","publication_status":"published","title":"Disjoint tree-compatible plane perfect matchings","status":"public","department":[{"_id":"KrCh"},{"_id":"UlWa"}],"author":[{"full_name":"Aichholzer, Oswin","first_name":"Oswin","last_name":"Aichholzer"},{"full_name":"Obmann, Julia","last_name":"Obmann","first_name":"Julia"},{"id":"B593B804-1035-11EA-B4F1-947645A5BB83","last_name":"Patak","first_name":"Pavel","full_name":"Patak, Pavel"},{"first_name":"Daniel","last_name":"Perz","full_name":"Perz, Daniel"},{"first_name":"Josef","last_name":"Tkadlec","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef"}],"date_updated":"2024-03-05T09:00:07Z","date_created":"2024-03-05T08:57:17Z","oa_version":"Published Version","article_number":"56","type":"conference","abstract":[{"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.","lang":"eng"}],"publication":"36th European Workshop on Computational Geometry","main_file_link":[{"open_access":"1","url":"https://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_56.pdf"}],"oa":1,"citation":{"mla":"Aichholzer, Oswin, et al. “Disjoint Tree-Compatible Plane Perfect Matchings.” 36th European Workshop on Computational Geometry, 56, 2020.","short":"O. Aichholzer, J. Obmann, P. Patak, D. Perz, J. Tkadlec, in:, 36th European Workshop on Computational Geometry, 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.","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.","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.","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.","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."},"quality_controlled":"1","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","language":[{"iso":"eng"}],"month":"04","day":"01","article_processing_charge":"No"},{"abstract":[{"lang":"eng","text":"The genus g(G) of a graph G is the minimum g such that G has an embedding on the orientable surface M_g of genus g. A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z_2-genus of a graph G, denoted by g_0(G), is the minimum g such that G has an independently even drawing on M_g. By a result of Battle, Harary, Kodama and Youngs from 1962, the graph genus is additive over 2-connected blocks. In 2013, Schaefer and Stefankovic proved that the Z_2-genus of a graph is additive over 2-connected blocks as well, and asked whether this result can be extended to so-called 2-amalgamations, as an analogue of results by Decker, Glover, Huneke, and Stahl for the genus. We give the following partial answer. If G=G_1 cup G_2, G_1 and G_2 intersect in two vertices u and v, and G-u-v has k connected components (among which we count the edge uv if present), then |g_0(G)-(g_0(G_1)+g_0(G_2))|<=k+1. For complete bipartite graphs K_{m,n}, with n >= m >= 3, we prove that g_0(K_{m,n})/g(K_{m,n})=1-O(1/n). Similar results are proved also for the Euler Z_2-genus. We express the Z_2-genus of a graph using the minimum rank of partial symmetric matrices over Z_2; a problem that might be of independent interest. "}],"alternative_title":["LIPIcs"],"type":"conference","oa_version":"Published Version","file":[{"access_level":"open_access","file_name":"2019_LIPIcs_Fulek.pdf","creator":"dernst","file_size":628347,"content_type":"application/pdf","file_id":"7445","relation":"main_file","checksum":"aac37b09118cc0ab58cf77129e691f8c","date_created":"2020-02-04T09:14:31Z","date_updated":"2020-07-14T12:47:57Z"}],"intvolume":" 129","ddc":["000"],"title":"Z_2-Genus of graphs and minimum rank of partial symmetric matrices","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"7401","article_processing_charge":"No","has_accepted_license":"1","day":"01","scopus_import":1,"date_published":"2019-06-01T00:00:00Z","citation":{"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.","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.","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.","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","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.","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"},"publication":"35th International Symposium on Computational Geometry (SoCG 2019)","file_date_updated":"2020-07-14T12:47:57Z","article_number":"39","volume":129,"date_updated":"2021-01-12T08:13:24Z","date_created":"2020-01-29T16:17:05Z","author":[{"full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","first_name":"Radoslav"},{"full_name":"Kyncl, Jan","first_name":"Jan","last_name":"Kyncl"}],"department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","year":"2019","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-104-7"]},"month":"06","language":[{"iso":"eng"}],"doi":"10.4230/LIPICS.SOCG.2019.39","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2019-06-21","start_date":"2019-06-18","location":"Portland, OR, United States"},"project":[{"call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281"}],"quality_controlled":"1","external_id":{"arxiv":["1903.08637"]},"tmp":{"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)","image":"/images/cc_by.png"},"oa":1},{"page":"365-394","article_type":"original","citation":{"ama":"Chaplick S, Fulek R, Klavík P. Extending partial representations of circle graphs. Journal of Graph Theory. 2019;91(4):365-394. doi:10.1002/jgt.22436","ista":"Chaplick S, Fulek R, Klavík P. 2019. Extending partial representations of circle graphs. Journal of Graph Theory. 91(4), 365–394.","apa":"Chaplick, S., Fulek, R., & Klavík, P. (2019). Extending partial representations of circle graphs. Journal of Graph Theory. Wiley. https://doi.org/10.1002/jgt.22436","ieee":"S. Chaplick, R. Fulek, and P. Klavík, “Extending partial representations of circle graphs,” Journal of Graph Theory, vol. 91, no. 4. Wiley, pp. 365–394, 2019.","mla":"Chaplick, Steven, et al. “Extending Partial Representations of Circle Graphs.” Journal of Graph Theory, vol. 91, no. 4, Wiley, 2019, pp. 365–94, doi:10.1002/jgt.22436.","short":"S. Chaplick, R. Fulek, P. Klavík, Journal of Graph Theory 91 (2019) 365–394.","chicago":"Chaplick, Steven, Radoslav Fulek, and Pavel Klavík. “Extending Partial Representations of Circle Graphs.” Journal of Graph Theory. Wiley, 2019. https://doi.org/10.1002/jgt.22436."},"publication":"Journal of Graph Theory","date_published":"2019-08-01T00:00:00Z","scopus_import":"1","article_processing_charge":"No","day":"01","intvolume":" 91","title":"Extending partial representations of circle graphs","status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"5790","oa_version":"Preprint","type":"journal_article","issue":"4","abstract":[{"text":"The partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph G and a partial representation R′ giving some predrawn chords that represent an induced subgraph of G. The question is whether one can extend R′ to a representation R of the entire graph G, that is, whether one can draw the remaining chords into a partially predrawn representation to obtain a representation of G. Our main result is an O(n3) time algorithm for partial representation extension of circle graphs, where n is the number of vertices. To show this, we describe the structure of all representations of a circle graph using split decomposition. This can be of independent interest.","lang":"eng"}],"project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","isi":1,"main_file_link":[{"url":"https://arxiv.org/abs/1309.2399","open_access":"1"}],"external_id":{"arxiv":["1309.2399"],"isi":["000485392800004"]},"oa":1,"language":[{"iso":"eng"}],"doi":"10.1002/jgt.22436","publication_identifier":{"issn":["03649024"]},"month":"08","department":[{"_id":"UlWa"}],"publisher":"Wiley","publication_status":"published","year":"2019","volume":91,"date_updated":"2023-08-24T14:30:43Z","date_created":"2018-12-30T22:59:15Z","author":[{"first_name":"Steven","last_name":"Chaplick","full_name":"Chaplick, Steven"},{"first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav"},{"full_name":"Klavík, Pavel","last_name":"Klavík","first_name":"Pavel"}],"ec_funded":1},{"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"433"}]},"author":[{"last_name":"Fulek","first_name":"Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav"},{"first_name":"János","last_name":"Pach","full_name":"Pach, János"}],"volume":259,"date_created":"2019-01-20T22:59:17Z","date_updated":"2023-08-24T14:39:33Z","year":"2019","department":[{"_id":"UlWa"}],"publisher":"Elsevier","publication_status":"published","publication_identifier":{"issn":["0166218X"]},"month":"04","doi":"10.1016/j.dam.2018.12.025","language":[{"iso":"eng"}],"external_id":{"arxiv":["1708.08037"],"isi":["000466061100020"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1708.08037"}],"oa":1,"project":[{"name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281"}],"quality_controlled":"1","isi":1,"issue":"4","abstract":[{"lang":"eng","text":"A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an odd number of times. It is also shown that the maximum number of edges of a quasi-thrackle on n vertices is [Formula presented](n−1), and that this bound is best possible for infinitely many values of n."}],"type":"journal_article","oa_version":"Preprint","_id":"5857","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","intvolume":" 259","title":"Thrackles: An improved upper bound","status":"public","article_processing_charge":"No","day":"30","scopus_import":"1","date_published":"2019-04-30T00:00:00Z","citation":{"ama":"Fulek R, Pach J. Thrackles: An improved upper bound. Discrete Applied Mathematics. 2019;259(4):266-231. doi:10.1016/j.dam.2018.12.025","ieee":"R. Fulek and J. Pach, “Thrackles: An improved upper bound,” Discrete Applied Mathematics, vol. 259, no. 4. Elsevier, pp. 266–231, 2019.","apa":"Fulek, R., & Pach, J. (2019). Thrackles: An improved upper bound. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2018.12.025","ista":"Fulek R, Pach J. 2019. Thrackles: An improved upper bound. Discrete Applied Mathematics. 259(4), 266–231.","short":"R. Fulek, J. Pach, Discrete Applied Mathematics 259 (2019) 266–231.","mla":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” Discrete Applied Mathematics, vol. 259, no. 4, Elsevier, 2019, pp. 266–231, doi:10.1016/j.dam.2018.12.025.","chicago":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” Discrete Applied Mathematics. Elsevier, 2019. https://doi.org/10.1016/j.dam.2018.12.025."},"publication":"Discrete Applied Mathematics","page":"266-231","article_type":"original"},{"article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2019-11-01T00:00:00Z","citation":{"ama":"Silva A, Arroyo Guevara AM, Richter B, Lee O. Graphs with at most one crossing. Discrete Mathematics. 2019;342(11):3201-3207. doi:10.1016/j.disc.2019.06.031","ieee":"A. Silva, A. M. Arroyo Guevara, B. Richter, and O. Lee, “Graphs with at most one crossing,” Discrete Mathematics, vol. 342, no. 11. Elsevier, pp. 3201–3207, 2019.","apa":"Silva, A., Arroyo Guevara, A. M., Richter, B., & Lee, O. (2019). Graphs with at most one crossing. Discrete Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2019.06.031","ista":"Silva A, Arroyo Guevara AM, Richter B, Lee O. 2019. Graphs with at most one crossing. Discrete Mathematics. 342(11), 3201–3207.","short":"A. Silva, A.M. Arroyo Guevara, B. Richter, O. Lee, Discrete Mathematics 342 (2019) 3201–3207.","mla":"Silva, André, et al. “Graphs with at Most One Crossing.” Discrete Mathematics, vol. 342, no. 11, Elsevier, 2019, pp. 3201–07, doi:10.1016/j.disc.2019.06.031.","chicago":"Silva, André , Alan M Arroyo Guevara, Bruce Richter, and Orlando Lee. “Graphs with at Most One Crossing.” Discrete Mathematics. Elsevier, 2019. https://doi.org/10.1016/j.disc.2019.06.031."},"publication":"Discrete Mathematics","page":"3201-3207","issue":"11","abstract":[{"lang":"eng","text":"The crossing number of a graph G is the least number of crossings over all possible drawings of G. We present a structural characterization of graphs with crossing number one."}],"type":"journal_article","oa_version":"Preprint","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"6638","intvolume":" 342","title":"Graphs with at most one crossing","status":"public","publication_identifier":{"issn":["0012-365X"]},"month":"11","doi":"10.1016/j.disc.2019.06.031","language":[{"iso":"eng"}],"external_id":{"arxiv":["1901.09955"],"isi":["000486358100025"]},"main_file_link":[{"url":"https://arxiv.org/abs/1901.09955","open_access":"1"}],"oa":1,"project":[{"name":"Reglas de Conectividad funcional en el hipocampo","_id":"26366136-B435-11E9-9278-68D0E5697425"},{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"}],"isi":1,"quality_controlled":"1","ec_funded":1,"author":[{"last_name":"Silva","first_name":"André ","full_name":"Silva, André "},{"full_name":"Arroyo Guevara, Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2401-8670","first_name":"Alan M","last_name":"Arroyo Guevara"},{"full_name":"Richter, Bruce","last_name":"Richter","first_name":"Bruce"},{"full_name":"Lee, Orlando","last_name":"Lee","first_name":"Orlando"}],"volume":342,"date_created":"2019-07-14T21:59:20Z","date_updated":"2023-08-29T06:31:41Z","year":"2019","publisher":"Elsevier","department":[{"_id":"UlWa"}],"publication_status":"published"},{"scopus_import":"1","article_processing_charge":"No","day":"29","citation":{"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.","short":"R. Fulek, J. Kynčl, Combinatorica 39 (2019) 1267–1279.","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","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.","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. Combinatorica. 2019;39(6):1267-1279. doi:10.1007/s00493-019-3905-7"},"publication":"Combinatorica","page":"1267-1279","article_type":"original","date_published":"2019-10-29T00:00:00Z","type":"journal_article","issue":"6","abstract":[{"lang":"eng","text":"We find a graph of genus 5 and its drawing on the orientable surface of genus 4 with every pair of independent edges crossing an even number of times. This shows that the strong Hanani–Tutte theorem cannot be extended to the orientable surface of genus 4. As a base step in the construction we use a counterexample to an extension of the unified Hanani–Tutte theorem on the torus."}],"_id":"7034","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","intvolume":" 39","title":"Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4","status":"public","oa_version":"Preprint","publication_identifier":{"issn":["0209-9683"],"eissn":["1439-6912"]},"month":"10","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1709.00508"}],"external_id":{"isi":["000493267200003"],"arxiv":["1709.00508"]},"oa":1,"project":[{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7"},{"grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs"}],"isi":1,"quality_controlled":"1","doi":"10.1007/s00493-019-3905-7","language":[{"iso":"eng"}],"ec_funded":1,"year":"2019","department":[{"_id":"UlWa"}],"publisher":"Springer Nature","publication_status":"published","author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","first_name":"Radoslav","last_name":"Fulek","full_name":"Fulek, Radoslav"},{"last_name":"Kynčl","first_name":"Jan","full_name":"Kynčl, Jan"}],"volume":39,"date_created":"2019-11-18T14:29:50Z","date_updated":"2023-08-30T07:26:25Z"},{"issue":"3","abstract":[{"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.","lang":"eng"}],"type":"journal_article","oa_version":"Preprint","_id":"7108","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","intvolume":" 66","title":"Shellability is NP-complete","status":"public","article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2019-06-01T00:00:00Z","citation":{"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.","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","ista":"Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. 2019. Shellability is NP-complete. Journal of the ACM. 66(3), 21.","short":"X. Goaoc, P. Patak, Z. Patakova, M. Tancer, U. Wagner, Journal of the ACM 66 (2019).","mla":"Goaoc, Xavier, et al. “Shellability Is NP-Complete.” Journal of the ACM, vol. 66, no. 3, 21, ACM, 2019, doi:10.1145/3314024.","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."},"publication":"Journal of the ACM","article_type":"original","article_number":"21","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"184"}]},"author":[{"first_name":"Xavier","last_name":"Goaoc","full_name":"Goaoc, Xavier"},{"full_name":"Patak, Pavel","id":"B593B804-1035-11EA-B4F1-947645A5BB83","last_name":"Patak","first_name":"Pavel"},{"last_name":"Patakova","first_name":"Zuzana","orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87","full_name":"Patakova, Zuzana"},{"full_name":"Tancer, Martin","first_name":"Martin","last_name":"Tancer"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli"}],"volume":66,"date_updated":"2023-09-06T11:10:58Z","date_created":"2019-11-26T10:13:59Z","year":"2019","department":[{"_id":"UlWa"}],"publisher":"ACM","publication_status":"published","publication_identifier":{"issn":["0004-5411"]},"month":"06","doi":"10.1145/3314024","language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/pdf/1711.08436.pdf"}],"external_id":{"arxiv":["1711.08436"],"isi":["000495406300007"]},"isi":1,"quality_controlled":"1"},{"oa":1,"external_id":{"arxiv":["1908.08129"],"isi":["000612918800018"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1908.08129"}],"quality_controlled":"1","isi":1,"project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"}],"conference":{"name":"GD: Graph Drawing and Network Visualization","end_date":"2019-09-20","start_date":"2019-09-17","location":"Prague, Czech Republic"},"doi":"10.1007/978-3-030-35802-0_18","language":[{"iso":"eng"}],"month":"11","publication_identifier":{"eissn":["1611-3349"],"isbn":["978-3-0303-5801-3"],"issn":["0302-9743"]},"year":"2019","publication_status":"published","publisher":"Springer Nature","department":[{"_id":"UlWa"}],"author":[{"full_name":"Arroyo Guevara, Alan M","orcid":"0000-0003-2401-8670","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","last_name":"Arroyo Guevara","first_name":"Alan M"},{"full_name":"Derka, Martin","last_name":"Derka","first_name":"Martin"},{"first_name":"Irene","last_name":"Parada","full_name":"Parada, Irene"}],"date_created":"2020-01-05T23:00:47Z","date_updated":"2023-09-06T14:56:00Z","volume":11904,"ec_funded":1,"publication":"27th International Symposium on Graph Drawing and Network Visualization","citation":{"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.","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.","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","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.","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."},"page":"230-243","date_published":"2019-11-28T00:00:00Z","scopus_import":"1","day":"28","article_processing_charge":"No","_id":"7230","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","title":"Extending simple drawings","intvolume":" 11904","oa_version":"Preprint","type":"conference","alternative_title":["LNCS"],"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"}]},{"date_published":"2019-08-08T00:00:00Z","citation":{"apa":"Zhechev, S. Y. (2019). Algorithmic aspects of homotopy theory and embeddability. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:6681","ieee":"S. Y. Zhechev, “Algorithmic aspects of homotopy theory and embeddability,” Institute of Science and Technology Austria, 2019.","ista":"Zhechev SY. 2019. Algorithmic aspects of homotopy theory and embeddability. Institute of Science and Technology Austria.","ama":"Zhechev SY. Algorithmic aspects of homotopy theory and embeddability. 2019. doi:10.15479/AT:ISTA:6681","chicago":"Zhechev, Stephan Y. “Algorithmic Aspects of Homotopy Theory and Embeddability.” Institute of Science and Technology Austria, 2019. https://doi.org/10.15479/AT:ISTA:6681.","short":"S.Y. Zhechev, Algorithmic Aspects of Homotopy Theory and Embeddability, Institute of Science and Technology Austria, 2019.","mla":"Zhechev, Stephan Y. Algorithmic Aspects of Homotopy Theory and Embeddability. Institute of Science and Technology Austria, 2019, doi:10.15479/AT:ISTA:6681."},"page":"104","article_processing_charge":"No","has_accepted_license":"1","day":"08","file":[{"file_size":1464227,"content_type":"application/pdf","creator":"szhechev","file_name":"Stephan_Zhechev_thesis.pdf","access_level":"open_access","date_updated":"2020-07-14T12:47:37Z","date_created":"2019-08-07T13:02:50Z","checksum":"3231e7cbfca3b5687366f84f0a57a0c0","relation":"main_file","file_id":"6771"},{"file_id":"6772","relation":"source_file","checksum":"85d65eb27b4377a9e332ee37a70f08b6","date_created":"2019-08-07T13:03:22Z","date_updated":"2020-07-14T12:47:37Z","access_level":"closed","file_name":"Stephan_Zhechev_thesis.tex","creator":"szhechev","file_size":303988,"content_type":"application/octet-stream"},{"creator":"szhechev","content_type":"application/zip","file_size":1087004,"access_level":"closed","file_name":"supplementary_material.zip","checksum":"86b374d264ca2dd53e712728e253ee75","date_created":"2019-08-07T13:03:34Z","date_updated":"2020-07-14T12:47:37Z","file_id":"6773","relation":"supplementary_material"}],"oa_version":"Published Version","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"6681","title":"Algorithmic aspects of homotopy theory and embeddability","status":"public","ddc":["514"],"abstract":[{"lang":"eng","text":"The first part of the thesis considers the computational aspects of the homotopy groups πd(X) of a topological space X. It is well known that there is no algorithm to decide whether the fundamental group π1(X) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute the higher homotopy group πd(X) for any given d ≥ 2.\r\nHowever, these algorithms come with a caveat: They compute the isomorphism type of πd(X), d ≥ 2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πd(X). We present an algorithm that, given a simply connected space X, computes πd(X) and represents its elements as simplicial maps from suitable triangulations of the d-sphere Sd to X. For fixed d, the algorithm runs in time exponential in size(X), the number of simplices of X. Moreover, we prove that this is optimal: For every fixed d ≥ 2,\r\nwe construct a family of simply connected spaces X such that for any simplicial map representing a generator of πd(X), the size of the triangulation of S d on which the map is defined, is exponential in size(X).\r\nIn the second part of the thesis, we prove that the following question is algorithmically undecidable for d < ⌊3(k+1)/2⌋, k ≥ 5 and (k, d) ̸= (5, 7), which covers essentially everything outside the meta-stable range: Given a finite simplicial complex K of dimension k, decide whether there exists a piecewise-linear (i.e., linear on an arbitrarily fine subdivision of K) embedding f : K ↪→ Rd of K into a d-dimensional Euclidean space."}],"type":"dissertation","alternative_title":["ISTA Thesis"],"doi":"10.15479/AT:ISTA:6681","language":[{"iso":"eng"}],"degree_awarded":"PhD","supervisor":[{"first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"oa":1,"tmp":{"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)","image":"/images/cc_by.png"},"publication_identifier":{"issn":["2663-337X"]},"month":"08","related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"6774"}]},"author":[{"last_name":"Zhechev","first_name":"Stephan Y","id":"3AA52972-F248-11E8-B48F-1D18A9856A87","full_name":"Zhechev, Stephan Y"}],"date_updated":"2023-09-07T13:10:36Z","date_created":"2019-07-26T11:14:34Z","year":"2019","publisher":"Institute of Science and Technology Austria","department":[{"_id":"UlWa"}],"publication_status":"published","file_date_updated":"2020-07-14T12:47:37Z"},{"project":[{"grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF"}],"publication":"arXiv","main_file_link":[{"url":"https://arxiv.org/abs/1910.12628","open_access":"1"}],"citation":{"mla":"Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions and the Mapping Degree.” ArXiv, 1910.12628, arXiv.","short":"S. Avvakumov, S. Kudrya, ArXiv (n.d.).","chicago":"Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions and the Mapping Degree.” ArXiv. arXiv, n.d.","ama":"Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping degree. arXiv.","ista":"Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping degree. arXiv, 1910.12628.","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."},"external_id":{"arxiv":["1910.12628"]},"oa":1,"language":[{"iso":"eng"}],"date_published":"2019-10-28T00:00:00Z","month":"10","day":"28","article_processing_charge":"No","title":"Vanishing of all equivariant obstructions and the mapping degree","status":"public","publication_status":"submitted","department":[{"_id":"UlWa"}],"publisher":"arXiv","_id":"8182","year":"2019","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-09-07T13:12:17Z","date_created":"2020-07-30T10:45:08Z","oa_version":"Preprint","author":[{"full_name":"Avvakumov, Sergey","first_name":"Sergey","last_name":"Avvakumov","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kudrya, Sergey","last_name":"Kudrya","first_name":"Sergey","id":"ecf01965-d252-11ea-95a5-8ada5f6c6a67"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"11446"},{"id":"8156","status":"public","relation":"dissertation_contains"}]},"article_number":"1910.12628","type":"preprint","abstract":[{"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.","lang":"eng"}]},{"status":"public","title":"Envy-free division using mapping degree","publication_status":"submitted","department":[{"_id":"UlWa"}],"year":"2019","_id":"8185","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-09-07T13:12:17Z","date_created":"2020-07-30T10:45:51Z","oa_version":"Preprint","author":[{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","last_name":"Avvakumov","first_name":"Sergey","full_name":"Avvakumov, Sergey"},{"first_name":"Roman","last_name":"Karasev","full_name":"Karasev, Roman"}],"related_material":{"record":[{"id":"8156","relation":"dissertation_contains","status":"public"}],"link":[{"relation":"later_version","url":"https://doi.org/10.1112/mtk.12059"}]},"article_number":"1907.11183","type":"preprint","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."}],"project":[{"call_identifier":"FWF","name":"Algorithms for Embeddings and Homotopy Theory","grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425"}],"publication":"arXiv","oa":1,"external_id":{"arxiv":["1907.11183"]},"citation":{"chicago":"Avvakumov, Sergey, and Roman Karasev. “Envy-Free Division Using Mapping Degree.” ArXiv, n.d. https://doi.org/10.48550/arXiv.1907.11183.","short":"S. Avvakumov, R. Karasev, ArXiv (n.d.).","mla":"Avvakumov, Sergey, and Roman Karasev. “Envy-Free Division Using Mapping Degree.” ArXiv, 1907.11183, doi:10.48550/arXiv.1907.11183.","apa":"Avvakumov, S., & Karasev, R. (n.d.). Envy-free division using mapping degree. arXiv. https://doi.org/10.48550/arXiv.1907.11183","ieee":"S. Avvakumov and R. Karasev, “Envy-free division using mapping degree,” arXiv. .","ista":"Avvakumov S, Karasev R. Envy-free division using mapping degree. arXiv, 1907.11183.","ama":"Avvakumov S, Karasev R. Envy-free division using mapping degree. arXiv. doi:10.48550/arXiv.1907.11183"},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1907.11183"}],"language":[{"iso":"eng"}],"date_published":"2019-07-25T00:00:00Z","doi":"10.48550/arXiv.1907.11183","month":"07","day":"25","article_processing_charge":"No"},{"file_date_updated":"2020-07-14T12:47:14Z","date_created":"2019-02-14T11:54:08Z","date_updated":"2023-09-07T13:17:36Z","volume":61,"author":[{"last_name":"Lubiw","first_name":"Anna","full_name":"Lubiw, Anna"},{"full_name":"Masárová, Zuzana","first_name":"Zuzana","last_name":"Masárová","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322"},{"last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"related_material":{"record":[{"id":"683","status":"public","relation":"earlier_version"},{"id":"7944","status":"public","relation":"dissertation_contains"}]},"publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Springer Nature","year":"2019","month":"06","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"language":[{"iso":"eng"}],"doi":"10.1007/s00454-018-0035-8","isi":1,"quality_controlled":"1","project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"tmp":{"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)","image":"/images/cc_by.png"},"external_id":{"isi":["000466130000009"],"arxiv":["1710.02741"]},"oa":1,"abstract":[{"text":"Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm (with 𝑂(𝑛8) being a crude bound on the run-time) to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of 𝑂(𝑛7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture.","lang":"eng"}],"issue":"4","type":"journal_article","file":[{"date_created":"2019-02-14T11:57:22Z","date_updated":"2020-07-14T12:47:14Z","checksum":"e1bff88f1d77001b53b78c485ce048d7","relation":"main_file","file_id":"5988","file_size":556276,"content_type":"application/pdf","creator":"dernst","file_name":"2018_DiscreteGeometry_Lubiw.pdf","access_level":"open_access"}],"oa_version":"Published Version","ddc":["000"],"status":"public","title":"A proof of the orbit conjecture for flipping edge-labelled triangulations","intvolume":" 61","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"5986","day":"01","has_accepted_license":"1","article_processing_charge":"Yes (via OA deal)","scopus_import":"1","date_published":"2019-06-01T00:00:00Z","article_type":"original","page":"880-898","publication":"Discrete & Computational Geometry","citation":{"chicago":"Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” Discrete & Computational Geometry. Springer Nature, 2019. https://doi.org/10.1007/s00454-018-0035-8.","short":"A. Lubiw, Z. Masárová, U. Wagner, Discrete & Computational Geometry 61 (2019) 880–898.","mla":"Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” Discrete & Computational Geometry, vol. 61, no. 4, Springer Nature, 2019, pp. 880–98, doi:10.1007/s00454-018-0035-8.","apa":"Lubiw, A., Masárová, Z., & Wagner, U. (2019). A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-018-0035-8","ieee":"A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for flipping edge-labelled triangulations,” Discrete & Computational Geometry, vol. 61, no. 4. Springer Nature, pp. 880–898, 2019.","ista":"Lubiw A, Masárová Z, Wagner U. 2019. A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete & Computational Geometry. 61(4), 880–898.","ama":"Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete & Computational Geometry. 2019;61(4):880-898. doi:10.1007/s00454-018-0035-8"}},{"file_date_updated":"2020-07-14T12:47:33Z","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2019","date_created":"2019-06-11T20:09:57Z","date_updated":"2023-09-07T13:18:26Z","volume":129,"author":[{"id":"33C26278-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5445-5057","first_name":"Kristóf","last_name":"Huszár","full_name":"Huszár, Kristóf"},{"first_name":"Jonathan","last_name":"Spreer","full_name":"Spreer, Jonathan"}],"related_material":{"record":[{"id":"8032","status":"public","relation":"part_of_dissertation"}]},"month":"06","publication_identifier":{"isbn":["978-3-95977-104-7"],"issn":["1868-8969"]},"quality_controlled":"1","tmp":{"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)","image":"/images/cc_by.png"},"external_id":{"arxiv":["1812.05528"]},"oa":1,"language":[{"iso":"eng"}],"conference":{"end_date":"2019-06-21","location":"Portland, Oregon, United States","start_date":"2019-06-18","name":"SoCG: Symposium on Computational Geometry"},"doi":"10.4230/LIPIcs.SoCG.2019.44","alternative_title":["LIPIcs"],"type":"conference","abstract":[{"text":"Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined to be the minimum treewidth of the face pairing graph of any triangulation T of M. In this setting the relationship between the topology of a 3-manifold and its treewidth is of particular interest. First, as a corollary of work of Jaco and Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination with our earlier work with Wagner, this yields that for non-Haken manifolds the Heegaard genus and the treewidth are within a constant factor. Second, we characterize all 3-manifolds of treewidth one: These are precisely the lens spaces and a single other Seifert fibered space. Furthermore, we show that all remaining orientable Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth two. In particular, for every spherical 3-manifold we exhibit a triangulation of treewidth at most two. Our results further validate the parameter of treewidth (and other related parameters such as cutwidth or congestion) to be useful for topological computing, and also shed more light on the scope of existing FPT-algorithms in the field.","lang":"eng"}],"status":"public","title":"3-manifold triangulations with small treewidth","ddc":["516"],"intvolume":" 129","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6556","file":[{"file_name":"2019_LIPIcs-Huszar.pdf","access_level":"open_access","file_size":905885,"content_type":"application/pdf","creator":"kschuh","relation":"main_file","file_id":"6557","date_created":"2019-06-12T06:45:33Z","date_updated":"2020-07-14T12:47:33Z","checksum":"29d18c435368468aa85823dabb157e43"}],"oa_version":"Published Version","keyword":["computational 3-manifold topology","fixed-parameter tractability","layered triangulations","structural graph theory","treewidth","cutwidth","Heegaard genus"],"scopus_import":"1","day":"01","article_processing_charge":"No","has_accepted_license":"1","page":"44:1-44:20","publication":"35th International Symposium on Computational Geometry","citation":{"ista":"Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth. 35th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 44:1-44:20.","apa":"Huszár, K., & Spreer, J. (2019). 3-manifold triangulations with small treewidth. In 35th International Symposium on Computational Geometry (Vol. 129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2019.44","ieee":"K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,” in 35th International Symposium on Computational Geometry, Portland, Oregon, United States, 2019, vol. 129, p. 44:1-44:20.","ama":"Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: 35th International Symposium on Computational Geometry. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:44:1-44:20. doi:10.4230/LIPIcs.SoCG.2019.44","chicago":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” In 35th International Symposium on Computational Geometry, 129:44:1-44:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPIcs.SoCG.2019.44.","mla":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” 35th International Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20, doi:10.4230/LIPIcs.SoCG.2019.44.","short":"K. Huszár, J. Spreer, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20."},"date_published":"2019-06-01T00:00:00Z"},{"article_processing_charge":"No","has_accepted_license":"1","day":"01","citation":{"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.","short":"K. Huszár, J. Spreer, U. Wagner, Journal of Computational Geometry 10 (2019) 70–98.","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.","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","ista":"Huszár K, Spreer J, Wagner U. 2019. On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. 10(2), 70–98.","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."},"publication":"Journal of Computational Geometry","page":"70–98","article_type":"original","date_published":"2019-11-01T00:00:00Z","type":"journal_article","issue":"2","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"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"7093","intvolume":" 10","ddc":["514"],"status":"public","title":"On the treewidth of triangulated 3-manifolds","oa_version":"Published Version","file":[{"file_id":"7094","relation":"main_file","date_created":"2019-11-23T12:35:16Z","date_updated":"2020-07-14T12:47:49Z","checksum":"c872d590d38d538404782bca20c4c3f5","file_name":"479-1917-1-PB.pdf","access_level":"open_access","creator":"khuszar","content_type":"application/pdf","file_size":857590}],"publication_identifier":{"issn":["1920-180X"]},"month":"11","oa":1,"tmp":{"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)","image":"/images/cc_by.png"},"external_id":{"arxiv":["1712.00434"]},"quality_controlled":"1","doi":"10.20382/JOGC.V10I2A5","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:47:49Z","year":"2019","department":[{"_id":"UlWa"}],"publisher":"Computational Geometry Laborartoy","publication_status":"published","related_material":{"record":[{"id":"285","relation":"earlier_version","status":"public"},{"relation":"part_of_dissertation","status":"public","id":"8032"}]},"author":[{"full_name":"Huszár, Kristóf","id":"33C26278-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5445-5057","first_name":"Kristóf","last_name":"Huszár"},{"last_name":"Spreer","first_name":"Jonathan","full_name":"Spreer, Jonathan"},{"full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"volume":10,"date_updated":"2023-09-07T13:18:26Z","date_created":"2019-11-23T12:14:09Z"},{"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"}],"type":"preprint","article_number":"1908.08731","oa_version":"Preprint","date_created":"2020-07-30T10:45:34Z","date_updated":"2023-09-08T11:20:02Z","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"8156"}]},"author":[{"full_name":"Avvakumov, Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey","last_name":"Avvakumov"},{"full_name":"Karasev, R.","first_name":"R.","last_name":"Karasev"},{"full_name":"Skopenkov, A.","first_name":"A.","last_name":"Skopenkov"}],"department":[{"_id":"UlWa"}],"publisher":"arXiv","title":"Stronger counterexamples to the topological Tverberg conjecture","publication_status":"submitted","status":"public","_id":"8184","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","year":"2019","acknowledgement":"We would like to thank F. Frick for helpful discussions","article_processing_charge":"No","day":"23","month":"08","language":[{"iso":"eng"}],"date_published":"2019-08-23T00:00:00Z","project":[{"grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Algorithms for Embeddings and Homotopy Theory"}],"isi":1,"external_id":{"isi":["000986519600004"],"arxiv":["1908.08731"]},"oa":1,"citation":{"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.","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.","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.","short":"S. Avvakumov, R. Karasev, A. Skopenkov, ArXiv (n.d.)."},"main_file_link":[{"url":"https://arxiv.org/abs/1908.08731","open_access":"1"}],"publication":"arXiv"},{"scopus_import":1,"day":"01","citation":{"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.","short":"H. Akitaya, R. Fulek, C. Tóth, ACM Transactions on Algorithms 15 (2019).","ista":"Akitaya H, Fulek R, Tóth C. 2019. Recognizing weak embeddings of graphs. ACM Transactions on Algorithms. 15(4), 50.","ieee":"H. Akitaya, R. Fulek, and C. Tóth, “Recognizing weak embeddings of graphs,” ACM Transactions on Algorithms, vol. 15, no. 4. ACM, 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","ama":"Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. ACM Transactions on Algorithms. 2019;15(4). doi:10.1145/3344549"},"publication":"ACM Transactions on Algorithms","article_type":"original","date_published":"2019-10-01T00:00:00Z","type":"journal_article","issue":"4","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"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6982","intvolume":" 15","title":"Recognizing weak embeddings of graphs","status":"public","oa_version":"Preprint","month":"10","external_id":{"arxiv":["1709.09209"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1709.09209"}],"project":[{"name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","doi":"10.1145/3344549","language":[{"iso":"eng"}],"article_number":"50","year":"2019","publisher":"ACM","department":[{"_id":"UlWa"}],"publication_status":"published","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"309"}]},"author":[{"full_name":"Akitaya, Hugo","first_name":"Hugo","last_name":"Akitaya"},{"full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","first_name":"Radoslav"},{"full_name":"Tóth, Csaba","last_name":"Tóth","first_name":"Csaba"}],"volume":15,"date_updated":"2023-09-15T12:19:31Z","date_created":"2019-11-04T15:45:17Z"},{"file_date_updated":"2020-07-14T12:47:35Z","date_updated":"2023-12-13T12:03:35Z","date_created":"2019-07-17T10:35:04Z","volume":129,"author":[{"first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav"},{"last_name":"Gärtner","first_name":"Bernd","full_name":"Gärtner, Bernd"},{"full_name":"Kupavskii, Andrey","last_name":"Kupavskii","first_name":"Andrey"},{"full_name":"Valtr, Pavel","last_name":"Valtr","first_name":"Pavel"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner","full_name":"Wagner, Uli"}],"related_material":{"record":[{"id":"13974","status":"public","relation":"later_version"}]},"publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2019","month":"06","publication_identifier":{"isbn":["9783959771047"],"issn":["1868-8969"]},"language":[{"iso":"eng"}],"conference":{"name":"SoCG 2019: Symposium on Computational Geometry","start_date":"2019-06-18","location":"Portland, OR, United States","end_date":"2019-06-21"},"doi":"10.4230/LIPICS.SOCG.2019.38","quality_controlled":"1","project":[{"call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"tmp":{"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)","image":"/images/cc_by.png"},"external_id":{"arxiv":["1812.04911"]},"oa":1,"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"}],"alternative_title":["LIPIcs"],"type":"conference","file":[{"access_level":"open_access","file_name":"2019_LIPICS_Fulek.pdf","creator":"dernst","content_type":"application/pdf","file_size":559837,"file_id":"6667","relation":"main_file","checksum":"d6d017f8b41291b94d102294fa96ae9c","date_created":"2019-07-24T06:54:52Z","date_updated":"2020-07-14T12:47:35Z"}],"oa_version":"Published Version","ddc":["000","510"],"status":"public","title":"The crossing Tverberg theorem","intvolume":" 129","_id":"6647","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","has_accepted_license":"1","scopus_import":1,"date_published":"2019-06-01T00:00:00Z","page":"38:1-38:13","publication":"35th International Symposium on Computational Geometry","citation":{"ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. In: 35th International Symposium on Computational Geometry. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:38:1-38:13. doi:10.4230/LIPICS.SOCG.2019.38","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.","ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” in 35th International Symposium on Computational Geometry, Portland, OR, United States, 2019, vol. 129, p. 38:1-38:13.","apa":"Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2019). The crossing Tverberg theorem. In 35th International Symposium on Computational Geometry (Vol. 129, p. 38:1-38:13). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.38","mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” 35th International Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13, doi:10.4230/LIPICS.SOCG.2019.38.","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 35th International Symposium on Computational Geometry, 129:38:1-38:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.SOCG.2019.38."}},{"oa_version":"Preprint","date_created":"2020-06-08T12:25:25Z","date_updated":"2024-01-04T12:42:08Z","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"7944"},{"id":"12833","relation":"later_version","status":"public"}]},"author":[{"first_name":"Ahmad","last_name":"Biniaz","full_name":"Biniaz, Ahmad"},{"first_name":"Kshitij","last_name":"Jain","full_name":"Jain, Kshitij"},{"full_name":"Lubiw, Anna","first_name":"Anna","last_name":"Lubiw"},{"first_name":"Zuzana","last_name":"Masárová","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322","full_name":"Masárová, Zuzana"},{"full_name":"Miltzow, Tillmann","last_name":"Miltzow","first_name":"Tillmann"},{"full_name":"Mondal, Debajyoti","first_name":"Debajyoti","last_name":"Mondal"},{"full_name":"Naredla, Anurag Murty","first_name":"Anurag Murty","last_name":"Naredla"},{"orcid":"0000-0002-1097-9684","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","first_name":"Josef","full_name":"Tkadlec, Josef"},{"last_name":"Turcotte","first_name":"Alexi","full_name":"Turcotte, Alexi"}],"department":[{"_id":"HeEd"},{"_id":"UlWa"},{"_id":"KrCh"}],"status":"public","publication_status":"submitted","title":"Token swapping on trees","_id":"7950","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2019","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."}],"type":"preprint","article_number":"1903.06981","language":[{"iso":"eng"}],"date_published":"2019-03-16T00:00:00Z","citation":{"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.","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.","ama":"Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. arXiv.","apa":"Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte, A. (n.d.). Token swapping on trees. arXiv.","ieee":"A. Biniaz et al., “Token swapping on trees,” arXiv. .","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."},"main_file_link":[{"url":"https://arxiv.org/abs/1903.06981","open_access":"1"}],"external_id":{"arxiv":["1903.06981"]},"oa":1,"publication":"arXiv","article_processing_charge":"No","month":"03","day":"16"},{"file_date_updated":"2020-07-14T12:45:19Z","publist_id":"7735","article_number":"39","date_created":"2018-12-11T11:45:04Z","date_updated":"2021-01-12T06:53:36Z","volume":99,"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","last_name":"Kynčl","full_name":"Kynčl, Jan"}],"publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"year":"2018","month":"01","publication_identifier":{"isbn":["978-3-95977-066-8"]},"language":[{"iso":"eng"}],"conference":{"start_date":"2018-06-11","location":"Budapest, Hungary","end_date":"2018-06-14","name":"SoCG: Symposium on Computational Geometry"},"doi":"10.4230/LIPIcs.SoCG.2018.39","quality_controlled":"1","project":[{"_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF"}],"oa":1,"tmp":{"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)","image":"/images/cc_by.png"},"abstract":[{"text":"We resolve in the affirmative conjectures of A. Skopenkov and Repovš (1998), and M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the setting of approximating maps of graphs on 2-dimensional surfaces by embeddings. Our proof of this result is constructive and almost immediately implies an efficient algorithm for testing whether a given piecewise linear map of a graph in a surface is approximable by an embedding. More precisely, an instance of this problem consists of (i) a graph G whose vertices are partitioned into clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a region R of a 2-dimensional compact surface M given as the union of a set of pairwise disjoint discs corresponding to the clusters and a set of pairwise disjoint "pipes" corresponding to the bundles, connecting certain pairs of these discs. We are to decide whether G can be embedded inside M so that the vertices in every cluster are drawn in the corresponding disc, the edges in every bundle pass only through its corresponding pipe, and every edge crosses the boundary of each disc at most once.","lang":"eng"}],"alternative_title":["Leibniz International Proceedings in Information, LIPIcs"],"type":"conference","oa_version":"Published Version","file":[{"creator":"dernst","file_size":718857,"content_type":"application/pdf","file_name":"2018_LIPIcs_Fulek.pdf","access_level":"open_access","date_updated":"2020-07-14T12:45:19Z","date_created":"2018-12-17T12:33:52Z","checksum":"f1b94f1a75b37c414a1f61d59fb2cd4c","file_id":"5701","relation":"main_file"}],"title":"Hanani-Tutte for approximating maps of graphs","ddc":["510"],"status":"public","intvolume":" 99","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"185","day":"01","has_accepted_license":"1","scopus_import":1,"date_published":"2018-01-01T00:00:00Z","citation":{"mla":"Fulek, Radoslav, and Jan Kynčl. Hanani-Tutte for Approximating Maps of Graphs. Vol. 99, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPIcs.SoCG.2018.39.","short":"R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","chicago":"Fulek, Radoslav, and Jan Kynčl. “Hanani-Tutte for Approximating Maps of Graphs,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.39.","ama":"Fulek R, Kynčl J. Hanani-Tutte for approximating maps of graphs. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPIcs.SoCG.2018.39","ista":"Fulek R, Kynčl J. 2018. Hanani-Tutte for approximating maps of graphs. SoCG: Symposium on Computational Geometry, Leibniz International Proceedings in Information, LIPIcs, vol. 99, 39.","apa":"Fulek, R., & Kynčl, J. (2018). Hanani-Tutte for approximating maps of graphs (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.39","ieee":"R. Fulek and J. Kynčl, “Hanani-Tutte for approximating maps of graphs,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99."}},{"month":"06","doi":"10.4230/LIPIcs.SoCG.2018.40","conference":{"end_date":"2018-06-14","location":"Budapest, Hungary","start_date":"2018-06-11","name":"SoCG: Symposium on Computational Geometry"},"language":[{"iso":"eng"}],"external_id":{"arxiv":["1803.05085"]},"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1803.05085","open_access":"1"}],"project":[{"grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425","name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF"}],"quality_controlled":"1","publist_id":"7734","related_material":{"record":[{"id":"11593","status":"public","relation":"later_version"}]},"author":[{"full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","first_name":"Radoslav"},{"full_name":"Kynčl, Jan","last_name":"Kynčl","first_name":"Jan"}],"volume":99,"date_created":"2018-12-11T11:45:05Z","date_updated":"2023-08-14T12:43:51Z","year":"2018","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"publication_status":"published","article_processing_charge":"No","day":"11","scopus_import":"1","date_published":"2018-06-11T00:00:00Z","citation":{"ama":"Fulek R, Kynčl J. The ℤ2-Genus of Kuratowski minors. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:40.1-40.14. doi:10.4230/LIPIcs.SoCG.2018.40","ista":"Fulek R, Kynčl J. 2018. The ℤ2-Genus of Kuratowski minors. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 40.1-40.14.","ieee":"R. Fulek and J. Kynčl, “The ℤ2-Genus of Kuratowski minors,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99, p. 40.1-40.14.","apa":"Fulek, R., & Kynčl, J. (2018). The ℤ2-Genus of Kuratowski minors (Vol. 99, p. 40.1-40.14). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.40","mla":"Fulek, Radoslav, and Jan Kynčl. The ℤ2-Genus of Kuratowski Minors. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 40.1-40.14, doi:10.4230/LIPIcs.SoCG.2018.40.","short":"R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 40.1-40.14.","chicago":"Fulek, Radoslav, and Jan Kynčl. “The ℤ2-Genus of Kuratowski Minors,” 99:40.1-40.14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.40."},"page":"40.1 - 40.14","abstract":[{"lang":"eng","text":"A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The ℤ2-genus of a graph G is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective t × t grid or one of the following so-called t-Kuratowski graphs: K3, t, or t copies of K5 or K3,3 sharing at most 2 common vertices. We show that the ℤ2-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its ℤ2-genus, solving a problem posed by Schaefer and Štefankovič, and giving an approximate version of the Hanani-Tutte theorem on orientable surfaces."}],"type":"conference","alternative_title":["LIPIcs"],"oa_version":"Submitted Version","_id":"186","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 99","title":"The ℤ2-Genus of Kuratowski minors","status":"public"},{"month":"01","oa":1,"external_id":{"arxiv":["1708.08037"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1708.08037"}],"quality_controlled":"1","conference":{"start_date":"201-09-25","location":"Boston, MA, United States","end_date":"2017-09-27","name":"GD 2017: Graph Drawing and Network Visualization"},"doi":"10.1007/978-3-319-73915-1_14","language":[{"iso":"eng"}],"publist_id":"7390","year":"2018","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Springer","author":[{"last_name":"Fulek","first_name":"Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav"},{"full_name":"Pach, János","last_name":"Pach","first_name":"János"}],"related_material":{"record":[{"status":"public","relation":"later_version","id":"5857"}]},"date_updated":"2023-08-24T14:39:32Z","date_created":"2018-12-11T11:46:27Z","volume":10692,"scopus_import":1,"day":"21","citation":{"ieee":"R. Fulek and J. Pach, “Thrackles: An improved upper bound,” presented at the GD 2017: Graph Drawing and Network Visualization, Boston, MA, United States, 2018, vol. 10692, pp. 160–166.","apa":"Fulek, R., & Pach, J. (2018). Thrackles: An improved upper bound (Vol. 10692, pp. 160–166). Presented at the GD 2017: Graph Drawing and Network Visualization, Boston, MA, United States: Springer. https://doi.org/10.1007/978-3-319-73915-1_14","ista":"Fulek R, Pach J. 2018. Thrackles: An improved upper bound. GD 2017: Graph Drawing and Network Visualization, LNCS, vol. 10692, 160–166.","ama":"Fulek R, Pach J. Thrackles: An improved upper bound. In: Vol 10692. Springer; 2018:160-166. doi:10.1007/978-3-319-73915-1_14","chicago":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound,” 10692:160–66. Springer, 2018. https://doi.org/10.1007/978-3-319-73915-1_14.","short":"R. Fulek, J. Pach, in:, Springer, 2018, pp. 160–166.","mla":"Fulek, Radoslav, and János Pach. Thrackles: An Improved Upper Bound. Vol. 10692, Springer, 2018, pp. 160–66, doi:10.1007/978-3-319-73915-1_14."},"page":"160 - 166","date_published":"2018-01-21T00:00:00Z","type":"conference","alternative_title":["LNCS"],"abstract":[{"lang":"eng","text":"A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an odd number of times. It is also shown that the maximum number of edges of a quasi-thrackle on n vertices is 3/2(n-1), and that this bound is best possible for infinitely many values of n."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"433","status":"public","title":"Thrackles: An improved upper bound","intvolume":" 10692","oa_version":"Submitted Version"},{"page":"41:1 - 41:16","citation":{"mla":"Goaoc, Xavier, et al. Shellability Is NP-Complete. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16, doi:10.4230/LIPIcs.SoCG.2018.41.","short":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16.","chicago":"Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Shellability Is NP-Complete,” 99:41:1-41:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.41.","ama":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:41:1-41:16. doi:10.4230/LIPIcs.SoCG.2018.41","ista":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2018. Shellability is NP-complete. SoCG: Symposium on Computational Geometry, Leibniz International Proceedings in Information, LIPIcs, vol. 99, 41:1-41:16.","ieee":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Shellability is NP-complete,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99, p. 41:1-41:16.","apa":"Goaoc, X., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2018). Shellability is NP-complete (Vol. 99, p. 41:1-41:16). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.41"},"date_published":"2018-06-11T00:00:00Z","scopus_import":1,"has_accepted_license":"1","day":"11","intvolume":" 99","status":"public","ddc":["516","000"],"title":"Shellability is NP-complete","_id":"184","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"file_name":"2018_LIPIcs_Goaoc.pdf","access_level":"open_access","content_type":"application/pdf","file_size":718414,"creator":"dernst","relation":"main_file","file_id":"5725","date_updated":"2020-07-14T12:45:18Z","date_created":"2018-12-17T16:35:02Z","checksum":"d12bdd60f04a57307867704b5f930afd"}],"oa_version":"Published Version","alternative_title":["Leibniz International Proceedings in Information, LIPIcs"],"type":"conference","abstract":[{"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.","lang":"eng"}],"quality_controlled":"1","oa":1,"tmp":{"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)","image":"/images/cc_by.png"},"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2018.41","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2018-06-14","start_date":"2018-06-11","location":"Budapest, Hungary"},"month":"06","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"publication_status":"published","acknowledgement":"Partially supported by the project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM) of Czech-French collaboration.","year":"2018","volume":99,"date_created":"2018-12-11T11:45:04Z","date_updated":"2023-09-06T11:10:57Z","related_material":{"record":[{"id":"7108","relation":"later_version","status":"public"}]},"author":[{"full_name":"Goaoc, Xavier","last_name":"Goaoc","first_name":"Xavier"},{"full_name":"Paták, Pavel","first_name":"Pavel","last_name":"Paták"},{"first_name":"Zuzana","last_name":"Patakova","id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683","full_name":"Patakova, Zuzana"},{"last_name":"Tancer","first_name":"Martin","orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","full_name":"Tancer, Martin"},{"first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"publist_id":"7736","file_date_updated":"2020-07-14T12:45:18Z"},{"scopus_import":1,"has_accepted_license":"1","article_processing_charge":"No","day":"01","citation":{"mla":"Huszár, Kristóf, et al. On the Treewidth of Triangulated 3-Manifolds. Vol. 99, 46, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPIcs.SoCG.2018.46.","short":"K. Huszár, J. Spreer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","chicago":"Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.46.","ama":"Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPIcs.SoCG.2018.46","ista":"Huszár K, Spreer J, Wagner U. 2018. On the treewidth of triangulated 3-manifolds. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 46.","ieee":"K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99.","apa":"Huszár, K., Spreer, J., & Wagner, U. (2018). On the treewidth of triangulated 3-manifolds (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.46"},"date_published":"2018-06-01T00:00:00Z","type":"conference","alternative_title":["LIPIcs"],"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. In view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs). We derive these results from work of Agol and of Scharlemann and Thompson, by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 48(k+1) (resp. 4(3k+1)).","lang":"eng"}],"_id":"285","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 99","title":"On the treewidth of triangulated 3-manifolds","status":"public","ddc":["516","000"],"oa_version":"Submitted Version","file":[{"checksum":"530d084116778135d5bffaa317479cac","date_created":"2018-12-17T15:32:38Z","date_updated":"2020-07-14T12:45:51Z","file_id":"5713","relation":"main_file","creator":"dernst","content_type":"application/pdf","file_size":642522,"access_level":"open_access","file_name":"2018_LIPIcs_Huszar.pdf"}],"publication_identifier":{"issn":["18688969"]},"month":"06","oa":1,"tmp":{"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)","image":"/images/cc_by.png"},"external_id":{"arxiv":["1712.00434"]},"quality_controlled":"1","doi":"10.4230/LIPIcs.SoCG.2018.46","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2018-06-14","start_date":"2018-06-11","location":"Budapest, Hungary"},"language":[{"iso":"eng"}],"article_number":"46","publist_id":"7614","file_date_updated":"2020-07-14T12:45:51Z","acknowledgement":"Research of the second author was supported by the Einstein Foundation (project “Einstein Visiting Fellow Santos”) and by the Simons Foundation (“Simons Visiting Professors” program).","year":"2018","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","related_material":{"record":[{"relation":"later_version","status":"public","id":"7093"}]},"author":[{"full_name":"Huszár, Kristóf","orcid":"0000-0002-5445-5057","id":"33C26278-F248-11E8-B48F-1D18A9856A87","last_name":"Huszár","first_name":"Kristóf"},{"full_name":"Spreer, Jonathan","first_name":"Jonathan","last_name":"Spreer"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli"}],"volume":99,"date_updated":"2023-09-06T11:13:41Z","date_created":"2018-12-11T11:45:37Z"},{"page":"177-231","article_type":"original","citation":{"ama":"Filakovský M, Franek P, Wagner U, Zhechev SY. Computing simplicial representatives of homotopy group elements. Journal of Applied and Computational Topology. 2018;2(3-4):177-231. doi:10.1007/s41468-018-0021-5","ieee":"M. Filakovský, P. Franek, U. Wagner, and S. Y. Zhechev, “Computing simplicial representatives of homotopy group elements,” Journal of Applied and Computational Topology, vol. 2, no. 3–4. Springer, pp. 177–231, 2018.","apa":"Filakovský, M., Franek, P., Wagner, U., & Zhechev, S. Y. (2018). Computing simplicial representatives of homotopy group elements. Journal of Applied and Computational Topology. Springer. https://doi.org/10.1007/s41468-018-0021-5","ista":"Filakovský M, Franek P, Wagner U, Zhechev SY. 2018. Computing simplicial representatives of homotopy group elements. Journal of Applied and Computational Topology. 2(3–4), 177–231.","short":"M. Filakovský, P. Franek, U. Wagner, S.Y. Zhechev, Journal of Applied and Computational Topology 2 (2018) 177–231.","mla":"Filakovský, Marek, et al. “Computing Simplicial Representatives of Homotopy Group Elements.” Journal of Applied and Computational Topology, vol. 2, no. 3–4, Springer, 2018, pp. 177–231, doi:10.1007/s41468-018-0021-5.","chicago":"Filakovský, Marek, Peter Franek, Uli Wagner, and Stephan Y Zhechev. “Computing Simplicial Representatives of Homotopy Group Elements.” Journal of Applied and Computational Topology. Springer, 2018. https://doi.org/10.1007/s41468-018-0021-5."},"publication":"Journal of Applied and Computational Topology","date_published":"2018-12-01T00:00:00Z","has_accepted_license":"1","day":"01","intvolume":" 2","status":"public","ddc":["514"],"title":"Computing simplicial representatives of homotopy group elements","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6774","oa_version":"Published Version","file":[{"creator":"dernst","content_type":"application/pdf","file_size":1056278,"file_name":"2018_JourAppliedComputTopology_Filakovsky.pdf","access_level":"open_access","date_created":"2019-08-08T06:55:21Z","date_updated":"2020-07-14T12:47:40Z","checksum":"cf9e7fcd2a113dd4828774fc75cdb7e8","file_id":"6775","relation":"main_file"}],"type":"journal_article","issue":"3-4","abstract":[{"lang":"eng","text":"A central problem of algebraic topology is to understand the homotopy groups 𝜋𝑑(𝑋) of a topological space X. For the computational version of the problem, it is well known that there is no algorithm to decide whether the fundamental group 𝜋1(𝑋) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with 𝜋1(𝑋) trivial), compute the higher homotopy group 𝜋𝑑(𝑋) for any given 𝑑≥2 . However, these algorithms come with a caveat: They compute the isomorphism type of 𝜋𝑑(𝑋) , 𝑑≥2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of 𝜋𝑑(𝑋) . Converting elements of this abstract group into explicit geometric maps from the d-dimensional sphere 𝑆𝑑 to X has been one of the main unsolved problems in the emerging field of computational homotopy theory. Here we present an algorithm that, given a simply connected space X, computes 𝜋𝑑(𝑋) and represents its elements as simplicial maps from a suitable triangulation of the d-sphere 𝑆𝑑 to X. For fixed d, the algorithm runs in time exponential in size(𝑋) , the number of simplices of X. Moreover, we prove that this is optimal: For every fixed 𝑑≥2 , we construct a family of simply connected spaces X such that for any simplicial map representing a generator of 𝜋𝑑(𝑋) , the size of the triangulation of 𝑆𝑑 on which the map is defined, is exponential in size(𝑋) ."}],"project":[{"call_identifier":"FWF","name":"Robust invariants of Nonlinear Systems","_id":"25F8B9BC-B435-11E9-9278-68D0E5697425","grant_number":"M01980"},{"_id":"3AC91DDA-15DF-11EA-824D-93A3E7B544D1","call_identifier":"FWF","name":"FWF Open Access Fund"}],"quality_controlled":"1","tmp":{"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)","image":"/images/cc_by.png"},"oa":1,"language":[{"iso":"eng"}],"doi":"10.1007/s41468-018-0021-5","publication_identifier":{"eissn":["2367-1734"],"issn":["2367-1726"]},"month":"12","publisher":"Springer","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2018","volume":2,"date_created":"2019-08-08T06:47:40Z","date_updated":"2023-09-07T13:10:36Z","related_material":{"record":[{"id":"6681","relation":"dissertation_contains","status":"public"}]},"author":[{"full_name":"Filakovský, Marek","first_name":"Marek","last_name":"Filakovský","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Peter","last_name":"Franek","id":"473294AE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8878-8397","full_name":"Franek, Peter"},{"first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"},{"id":"3AA52972-F248-11E8-B48F-1D18A9856A87","first_name":"Stephan Y","last_name":"Zhechev","full_name":"Zhechev, Stephan Y"}],"file_date_updated":"2020-07-14T12:47:40Z"},{"author":[{"full_name":"Fulek, Radoslav","first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774"},{"full_name":"Tóth, Csaba D.","last_name":"Tóth","first_name":"Csaba D."}],"date_updated":"2023-09-11T12:49:55Z","date_created":"2018-12-30T22:59:15Z","volume":"11282 ","year":"2018","publication_status":"published","publisher":"Springer","department":[{"_id":"UlWa"}],"conference":{"name":"Graph Drawing and Network Visualization","end_date":"2018-09-28","start_date":"2018-09-26","location":"Barcelona, Spain"},"doi":"10.1007/978-3-030-04414-5_16","language":[{"iso":"eng"}],"external_id":{"isi":["000672802500016"],"arxiv":["1808.07608"]},"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1808.07608","open_access":"1"}],"isi":1,"quality_controlled":"1","month":"12","publication_identifier":{"isbn":["9783030044138"]},"oa_version":"Preprint","_id":"5791","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","title":"Crossing minimization in perturbed drawings","abstract":[{"text":"Due to data compression or low resolution, nearby vertices and edges of a graph drawing may be bundled to a common node or arc. We model such a “compromised” drawing by a piecewise linear map φ:G → ℝ. We wish to perturb φ by an arbitrarily small ε>0 into a proper drawing (in which the vertices are distinct points, any two edges intersect in finitely many points, and no three edges have a common interior point) that minimizes the number of crossings. An ε-perturbation, for every ε>0, is given by a piecewise linear map (Formula Presented), where with ||·|| is the uniform norm (i.e., sup norm). We present a polynomial-time solution for this optimization problem when G is a cycle and the map φ has no spurs (i.e., no two adjacent edges are mapped to overlapping arcs). We also show that the problem becomes NP-complete (i) when G is an arbitrary graph and φ has no spurs, and (ii) when φ may have spurs and G is a cycle or a union of disjoint paths.","lang":"eng"}],"type":"conference","alternative_title":["LNCS"],"date_published":"2018-12-18T00:00:00Z","citation":{"ieee":"R. Fulek and C. D. Tóth, “Crossing minimization in perturbed drawings,” presented at the Graph Drawing and Network Visualization, Barcelona, Spain, 2018, vol. 11282, pp. 229–241.","apa":"Fulek, R., & Tóth, C. D. (2018). Crossing minimization in perturbed drawings (Vol. 11282, pp. 229–241). Presented at the Graph Drawing and Network Visualization, Barcelona, Spain: Springer. https://doi.org/10.1007/978-3-030-04414-5_16","ista":"Fulek R, Tóth CD. 2018. Crossing minimization in perturbed drawings. Graph Drawing and Network Visualization, LNCS, vol. 11282, 229–241.","ama":"Fulek R, Tóth CD. Crossing minimization in perturbed drawings. In: Vol 11282. Springer; 2018:229-241. doi:10.1007/978-3-030-04414-5_16","chicago":"Fulek, Radoslav, and Csaba D. Tóth. “Crossing Minimization in Perturbed Drawings,” 11282:229–41. Springer, 2018. https://doi.org/10.1007/978-3-030-04414-5_16.","short":"R. Fulek, C.D. Tóth, in:, Springer, 2018, pp. 229–241.","mla":"Fulek, Radoslav, and Csaba D. Tóth. Crossing Minimization in Perturbed Drawings. Vol. 11282, Springer, 2018, pp. 229–41, doi:10.1007/978-3-030-04414-5_16."},"page":"229-241","day":"18","article_processing_charge":"No","scopus_import":"1"},{"abstract":[{"text":"We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in R3? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which allows us to simplify X and recurse, is in proving that if X can be embedded in S3, then there is also an embedding in which X has a short meridian, that is, an essential curve in the boundary of X bounding a disk in S3 \\ X with length bounded by a computable function of the number of tetrahedra of X.","lang":"eng"}],"issue":"1","type":"journal_article","oa_version":"Preprint","title":"Embeddability in the 3-Sphere is decidable","status":"public","intvolume":" 65","_id":"425","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","day":"01","article_processing_charge":"No","scopus_import":"1","date_published":"2018-01-01T00:00:00Z","article_type":"original","publication":"Journal of the ACM","citation":{"chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Embeddability in the 3-Sphere Is Decidable.” Journal of the ACM. ACM, 2018. https://doi.org/10.1145/3078632.","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Journal of the ACM 65 (2018).","mla":"Matoušek, Jiří, et al. “Embeddability in the 3-Sphere Is Decidable.” Journal of the ACM, vol. 65, no. 1, 5, ACM, 2018, doi:10.1145/3078632.","apa":"Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2018). Embeddability in the 3-Sphere is decidable. Journal of the ACM. ACM. https://doi.org/10.1145/3078632","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Embeddability in the 3-Sphere is decidable,” Journal of the ACM, vol. 65, no. 1. ACM, 2018.","ista":"Matoušek J, Sedgwick E, Tancer M, Wagner U. 2018. Embeddability in the 3-Sphere is decidable. Journal of the ACM. 65(1), 5.","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Embeddability in the 3-Sphere is decidable. Journal of the ACM. 2018;65(1). doi:10.1145/3078632"},"publist_id":"7398","ec_funded":1,"article_number":"5","date_created":"2018-12-11T11:46:24Z","date_updated":"2023-09-11T13:38:49Z","volume":65,"author":[{"first_name":"Jiří","last_name":"Matoušek","full_name":"Matoušek, Jiří"},{"full_name":"Sedgwick, Eric","first_name":"Eric","last_name":"Sedgwick"},{"full_name":"Tancer, Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1191-6714","first_name":"Martin","last_name":"Tancer"},{"full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"2157"}]},"publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"ACM","year":"2018","month":"01","language":[{"iso":"eng"}],"doi":"10.1145/3078632","isi":1,"quality_controlled":"1","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"external_id":{"arxiv":["1402.0815"],"isi":["000425685900006"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1402.0815"}]},{"date_updated":"2023-09-15T12:19:32Z","date_created":"2018-12-11T11:45:45Z","author":[{"first_name":"Hugo","last_name":"Akitaya","full_name":"Akitaya, Hugo"},{"full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","first_name":"Radoslav","last_name":"Fulek"},{"full_name":"Tóth, Csaba","first_name":"Csaba","last_name":"Tóth"}],"related_material":{"record":[{"id":"6982","status":"public","relation":"later_version"}]},"publication_status":"published","publisher":"ACM","department":[{"_id":"UlWa"}],"year":"2018","acknowledgement":"∗Research supported in part by the NSF awards CCF-1422311 and CCF-1423615, and the Science Without Borders program. The second author gratefully acknowledges support from Austrian Science Fund (FWF): M2281-N35.","publist_id":"7556","language":[{"iso":"eng"}],"conference":{"start_date":"2018-01-07","location":"New Orleans, LA, USA","end_date":"2018-01-10","name":"SODA: Symposium on Discrete Algorithms"},"doi":"10.1137/1.9781611975031.20","quality_controlled":"1","isi":1,"project":[{"grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425","name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1709.09209"}],"oa":1,"external_id":{"arxiv":["1709.09209"],"isi":["000483921200021"]},"month":"01","oa_version":"Preprint","status":"public","title":"Recognizing weak embeddings of graphs","_id":"309","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","abstract":[{"lang":"eng","text":"We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding ' : G ! M of a graph G into a 2manifold M maps the vertices in V (G) to distinct points and the edges in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to a common node or arc, due to data compression or low resolution. This raises the computational problem of deciding whether a given map ' : G ! M comes from an embedding. A map ' : G ! M is a weak embedding if it can be perturbed into an embedding ψ: G ! M with k' \"k < \" for every " > 0. A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kyncl [14], which reduces to solving a system of linear equations over Z2. It runs in O(n2!) O(n4:75) time, where 2:373 is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O(n log n). Our algorithm is also conceptually simpler than [14]: We perform a sequence of local operations that gradually "untangles" the image '(G) into an embedding (G), or reports that ' is not a weak embedding. It generalizes a recent technique developed for the case that G is a cycle and the embedding is a simple polygon [1], and combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations."}],"type":"conference","date_published":"2018-01-01T00:00:00Z","page":"274 - 292","citation":{"mla":"Akitaya, Hugo, et al. Recognizing Weak Embeddings of Graphs. ACM, 2018, pp. 274–92, doi:10.1137/1.9781611975031.20.","short":"H. Akitaya, R. Fulek, C. Tóth, in:, ACM, 2018, pp. 274–292.","chicago":"Akitaya, Hugo, Radoslav Fulek, and Csaba Tóth. “Recognizing Weak Embeddings of Graphs,” 274–92. ACM, 2018. https://doi.org/10.1137/1.9781611975031.20.","ama":"Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. In: ACM; 2018:274-292. doi:10.1137/1.9781611975031.20","ista":"Akitaya H, Fulek R, Tóth C. 2018. Recognizing weak embeddings of graphs. SODA: Symposium on Discrete Algorithms, 274–292.","apa":"Akitaya, H., Fulek, R., & Tóth, C. (2018). Recognizing weak embeddings of graphs (pp. 274–292). Presented at the SODA: Symposium on Discrete Algorithms, New Orleans, LA, USA: ACM. https://doi.org/10.1137/1.9781611975031.20","ieee":"H. Akitaya, R. Fulek, and C. Tóth, “Recognizing weak embeddings of graphs,” presented at the SODA: Symposium on Discrete Algorithms, New Orleans, LA, USA, 2018, pp. 274–292."},"day":"01","article_processing_charge":"No","scopus_import":"1"},{"oa_version":"Preprint","intvolume":" 37","status":"public","title":"Proving the existence of loops in robot trajectories","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"5960","issue":"12","abstract":[{"lang":"eng","text":"In this paper we present a reliable method to verify the existence of loops along the uncertain trajectory of a robot, based on proprioceptive measurements only, within a bounded-error context. The loop closure detection is one of the key points in simultaneous localization and mapping (SLAM) methods, especially in homogeneous environments with difficult scenes recognitions. The proposed approach is generic and could be coupled with conventional SLAM algorithms to reliably reduce their computing burden, thus improving the localization and mapping processes in the most challenging environments such as unexplored underwater extents. To prove that a robot performed a loop whatever the uncertainties in its evolution, we employ the notion of topological degree that originates in the field of differential topology. We show that a verification tool based on the topological degree is an optimal method for proving robot loops. This is demonstrated both on datasets from real missions involving autonomous underwater vehicles and by a mathematical discussion."}],"type":"journal_article","date_published":"2018-10-24T00:00:00Z","page":"1500-1516","citation":{"ista":"Rohou S, Franek P, Aubry C, Jaulin L. 2018. Proving the existence of loops in robot trajectories. The International Journal of Robotics Research. 37(12), 1500–1516.","ieee":"S. Rohou, P. Franek, C. Aubry, and L. Jaulin, “Proving the existence of loops in robot trajectories,” The International Journal of Robotics Research, vol. 37, no. 12. SAGE Publications, pp. 1500–1516, 2018.","apa":"Rohou, S., Franek, P., Aubry, C., & Jaulin, L. (2018). Proving the existence of loops in robot trajectories. The International Journal of Robotics Research. SAGE Publications. https://doi.org/10.1177/0278364918808367","ama":"Rohou S, Franek P, Aubry C, Jaulin L. Proving the existence of loops in robot trajectories. The International Journal of Robotics Research. 2018;37(12):1500-1516. doi:10.1177/0278364918808367","chicago":"Rohou, Simon, Peter Franek, Clément Aubry, and Luc Jaulin. “Proving the Existence of Loops in Robot Trajectories.” The International Journal of Robotics Research. SAGE Publications, 2018. https://doi.org/10.1177/0278364918808367.","mla":"Rohou, Simon, et al. “Proving the Existence of Loops in Robot Trajectories.” The International Journal of Robotics Research, vol. 37, no. 12, SAGE Publications, 2018, pp. 1500–16, doi:10.1177/0278364918808367.","short":"S. Rohou, P. Franek, C. Aubry, L. Jaulin, The International Journal of Robotics Research 37 (2018) 1500–1516."},"publication":"The International Journal of Robotics Research","article_processing_charge":"No","day":"24","scopus_import":"1","volume":37,"date_updated":"2023-09-19T10:41:59Z","date_created":"2019-02-13T09:36:20Z","author":[{"first_name":"Simon","last_name":"Rohou","full_name":"Rohou, Simon"},{"full_name":"Franek, Peter","last_name":"Franek","first_name":"Peter","orcid":"0000-0001-8878-8397","id":"473294AE-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Aubry, Clément","first_name":"Clément","last_name":"Aubry"},{"first_name":"Luc","last_name":"Jaulin","full_name":"Jaulin, Luc"}],"department":[{"_id":"UlWa"}],"publisher":"SAGE Publications","publication_status":"published","year":"2018","language":[{"iso":"eng"}],"doi":"10.1177/0278364918808367","quality_controlled":"1","isi":1,"external_id":{"arxiv":["1712.01341"],"isi":["000456881100004"]},"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1712.01341","open_access":"1"}],"publication_identifier":{"eissn":["1741-3176"],"issn":["0278-3649"]},"month":"10"},{"language":[{"iso":"eng"}],"doi":"10.1017/fms.2018.7","isi":1,"quality_controlled":"1","project":[{"_id":"256E75B8-B435-11E9-9278-68D0E5697425","grant_number":"716117","name":"Optimal Transport and Stochastic Dynamics","call_identifier":"H2020"}],"tmp":{"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)","image":"/images/cc_by.png"},"external_id":{"arxiv":["1712.10205"],"isi":["000433915500001"]},"oa":1,"month":"05","publication_identifier":{"issn":["2050-5094"]},"date_created":"2019-04-30T06:09:57Z","date_updated":"2023-09-19T14:50:12Z","volume":6,"author":[{"orcid":"0000-0002-2548-617X","id":"430D2C90-F248-11E8-B48F-1D18A9856A87","last_name":"Akopyan","first_name":"Arseniy","full_name":"Akopyan, Arseniy"},{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey","last_name":"Avvakumov","full_name":"Avvakumov, Sergey"}],"related_material":{"record":[{"id":"8156","relation":"dissertation_contains","status":"public"}]},"publication_status":"published","department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"JaMa"}],"publisher":"Cambridge University Press","year":"2018","file_date_updated":"2020-07-14T12:47:28Z","ec_funded":1,"article_number":"e7","date_published":"2018-05-31T00:00:00Z","publication":"Forum of Mathematics, Sigma","citation":{"chicago":"Akopyan, Arseniy, and Sergey Avvakumov. “Any Cyclic Quadrilateral Can Be Inscribed in Any Closed Convex Smooth Curve.” Forum of Mathematics, Sigma. Cambridge University Press, 2018. https://doi.org/10.1017/fms.2018.7.","mla":"Akopyan, Arseniy, and Sergey Avvakumov. “Any Cyclic Quadrilateral Can Be Inscribed in Any Closed Convex Smooth Curve.” Forum of Mathematics, Sigma, vol. 6, e7, Cambridge University Press, 2018, doi:10.1017/fms.2018.7.","short":"A. Akopyan, S. Avvakumov, Forum of Mathematics, Sigma 6 (2018).","ista":"Akopyan A, Avvakumov S. 2018. Any cyclic quadrilateral can be inscribed in any closed convex smooth curve. Forum of Mathematics, Sigma. 6, e7.","ieee":"A. Akopyan and S. Avvakumov, “Any cyclic quadrilateral can be inscribed in any closed convex smooth curve,” Forum of Mathematics, Sigma, vol. 6. Cambridge University Press, 2018.","apa":"Akopyan, A., & Avvakumov, S. (2018). Any cyclic quadrilateral can be inscribed in any closed convex smooth curve. Forum of Mathematics, Sigma. Cambridge University Press. https://doi.org/10.1017/fms.2018.7","ama":"Akopyan A, Avvakumov S. Any cyclic quadrilateral can be inscribed in any closed convex smooth curve. Forum of Mathematics, Sigma. 2018;6. doi:10.1017/fms.2018.7"},"day":"31","article_processing_charge":"No","has_accepted_license":"1","file":[{"date_created":"2019-04-30T06:14:58Z","date_updated":"2020-07-14T12:47:28Z","checksum":"5a71b24ba712a3eb2e46165a38fbc30a","relation":"main_file","file_id":"6356","file_size":249246,"content_type":"application/pdf","creator":"dernst","file_name":"2018_ForumMahtematics_Akopyan.pdf","access_level":"open_access"}],"oa_version":"Published Version","status":"public","title":"Any cyclic quadrilateral can be inscribed in any closed convex smooth curve","ddc":["510"],"intvolume":" 6","_id":"6355","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","abstract":[{"lang":"eng","text":"We prove that any cyclic quadrilateral can be inscribed in any closed convex C1-curve. The smoothness condition is not required if the quadrilateral is a rectangle."}],"type":"journal_article"},{"issue":"1","abstract":[{"text":"We give a detailed and easily accessible proof of Gromov’s Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map (Formula presented.) there exists a point (Formula presented.) that is contained in the images of a positive fraction (Formula presented.) of the d-cells of X. More generally, the conclusion holds if (Formula presented.) is replaced by any d-dimensional piecewise-linear manifold M, with a constant (Formula presented.) that depends only on d and on the expansion properties of X, but not on M.","lang":"eng"}],"type":"journal_article","pubrep_id":"912","file":[{"relation":"main_file","file_id":"5835","date_created":"2019-01-15T13:44:05Z","date_updated":"2020-07-14T12:47:58Z","checksum":"d2f70fc132156504aa4c626aa378a7ab","file_name":"s10711-017-0291-4.pdf","access_level":"open_access","file_size":412486,"content_type":"application/pdf","creator":"kschuh"}],"oa_version":"Published Version","_id":"742","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","intvolume":" 195","title":"On expansion and topological overlap","ddc":["514","516"],"status":"public","has_accepted_license":"1","article_processing_charge":"Yes (via OA deal)","day":"01","scopus_import":"1","date_published":"2018-08-01T00:00:00Z","citation":{"mla":"Dotterrer, Dominic, et al. “On Expansion and Topological Overlap.” Geometriae Dedicata, vol. 195, no. 1, Springer, 2018, pp. 307–317, doi:10.1007/s10711-017-0291-4.","short":"D. Dotterrer, T. Kaufman, U. Wagner, Geometriae Dedicata 195 (2018) 307–317.","chicago":"Dotterrer, Dominic, Tali Kaufman, and Uli Wagner. “On Expansion and Topological Overlap.” Geometriae Dedicata. Springer, 2018. https://doi.org/10.1007/s10711-017-0291-4.","ama":"Dotterrer D, Kaufman T, Wagner U. On expansion and topological overlap. Geometriae Dedicata. 2018;195(1):307–317. doi:10.1007/s10711-017-0291-4","ista":"Dotterrer D, Kaufman T, Wagner U. 2018. On expansion and topological overlap. Geometriae Dedicata. 195(1), 307–317.","ieee":"D. Dotterrer, T. Kaufman, and U. Wagner, “On expansion and topological overlap,” Geometriae Dedicata, vol. 195, no. 1. Springer, pp. 307–317, 2018.","apa":"Dotterrer, D., Kaufman, T., & Wagner, U. (2018). On expansion and topological overlap. Geometriae Dedicata. Springer. https://doi.org/10.1007/s10711-017-0291-4"},"publication":"Geometriae Dedicata","page":"307–317","publist_id":"6925","file_date_updated":"2020-07-14T12:47:58Z","related_material":{"record":[{"id":"1378","relation":"earlier_version","status":"public"}]},"author":[{"full_name":"Dotterrer, Dominic","first_name":"Dominic","last_name":"Dotterrer"},{"last_name":"Kaufman","first_name":"Tali","full_name":"Kaufman, Tali"},{"last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"volume":195,"date_created":"2018-12-11T11:48:16Z","date_updated":"2023-09-27T12:29:57Z","year":"2018","publisher":"Springer","department":[{"_id":"UlWa"}],"publication_status":"published","month":"08","doi":"10.1007/s10711-017-0291-4","language":[{"iso":"eng"}],"tmp":{"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)","image":"/images/cc_by.png"},"oa":1,"external_id":{"isi":["000437122700017"]},"project":[{"grant_number":"PP00P2_138948","_id":"25FA3206-B435-11E9-9278-68D0E5697425","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics"}],"quality_controlled":"1","isi":1},{"article_type":"original","page":"135 - 154","publication":"Journal of Graph Algorithms and Applications","citation":{"ieee":"R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity,” Journal of Graph Algorithms and Applications, vol. 21, no. 1. Brown University, pp. 135–154, 2017.","apa":"Fulek, R., Pelsmajer, M., & Schaefer, M. (2017). Hanani-Tutte for radial planarity. Journal of Graph Algorithms and Applications. Brown University. https://doi.org/10.7155/jgaa.00408","ista":"Fulek R, Pelsmajer M, Schaefer M. 2017. Hanani-Tutte for radial planarity. Journal of Graph Algorithms and Applications. 21(1), 135–154.","ama":"Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity. Journal of Graph Algorithms and Applications. 2017;21(1):135-154. doi:10.7155/jgaa.00408","chicago":"Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte for Radial Planarity.” Journal of Graph Algorithms and Applications. Brown University, 2017. https://doi.org/10.7155/jgaa.00408.","short":"R. Fulek, M. Pelsmajer, M. Schaefer, Journal of Graph Algorithms and Applications 21 (2017) 135–154.","mla":"Fulek, Radoslav, et al. “Hanani-Tutte for Radial Planarity.” Journal of Graph Algorithms and Applications, vol. 21, no. 1, Brown University, 2017, pp. 135–54, doi:10.7155/jgaa.00408."},"date_published":"2017-01-01T00:00:00Z","scopus_import":1,"day":"01","has_accepted_license":"1","article_processing_charge":"No","ddc":["510"],"status":"public","title":"Hanani-Tutte for radial planarity","intvolume":" 21","_id":"1113","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","file":[{"success":1,"date_updated":"2019-10-24T10:54:37Z","date_created":"2019-10-24T10:54:37Z","relation":"main_file","file_id":"6967","file_size":573623,"content_type":"application/pdf","creator":"dernst","access_level":"open_access","file_name":"2017_JournalGraphAlgorithms_Fulek.pdf"}],"type":"journal_article","abstract":[{"lang":"eng","text":"A drawing of a graph G is radial if the vertices of G are placed on concentric circles C 1 , . . . , C k with common center c , and edges are drawn radially : every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Toth."}],"issue":"1","quality_controlled":"1","project":[{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"external_id":{"arxiv":["1608.08662"]},"oa":1,"language":[{"iso":"eng"}],"doi":"10.7155/jgaa.00408","month":"01","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Brown University","year":"2017","date_created":"2018-12-11T11:50:13Z","date_updated":"2023-02-23T10:05:57Z","volume":21,"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","first_name":"Radoslav","last_name":"Fulek","full_name":"Fulek, Radoslav"},{"full_name":"Pelsmajer, Michael","first_name":"Michael","last_name":"Pelsmajer"},{"full_name":"Schaefer, Marcus","first_name":"Marcus","last_name":"Schaefer"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"1164"},{"id":"1595","relation":"earlier_version","status":"public"}]},"file_date_updated":"2019-10-24T10:54:37Z","publist_id":"6254","ec_funded":1},{"day":"09","article_processing_charge":"No","scopus_import":1,"date_published":"2017-06-09T00:00:00Z","publication":"Discrete & Computational Geometry","citation":{"chicago":"Burton, Benjamin, Arnaud N de Mesmay, and Uli Wagner. “Finding Non-Orientable Surfaces in 3-Manifolds.” Discrete & Computational Geometry. Springer, 2017. https://doi.org/10.1007/s00454-017-9900-0.","short":"B. Burton, A.N. de Mesmay, U. Wagner, Discrete & Computational Geometry 58 (2017) 871–888.","mla":"Burton, Benjamin, et al. “Finding Non-Orientable Surfaces in 3-Manifolds.” Discrete & Computational Geometry, vol. 58, no. 4, Springer, 2017, pp. 871–88, doi:10.1007/s00454-017-9900-0.","apa":"Burton, B., de Mesmay, A. N., & Wagner, U. (2017). Finding non-orientable surfaces in 3-Manifolds. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-017-9900-0","ieee":"B. Burton, A. N. de Mesmay, and U. Wagner, “Finding non-orientable surfaces in 3-Manifolds,” Discrete & Computational Geometry, vol. 58, no. 4. Springer, pp. 871–888, 2017.","ista":"Burton B, de Mesmay AN, Wagner U. 2017. Finding non-orientable surfaces in 3-Manifolds. Discrete & Computational Geometry. 58(4), 871–888.","ama":"Burton B, de Mesmay AN, Wagner U. Finding non-orientable surfaces in 3-Manifolds. Discrete & Computational Geometry. 2017;58(4):871-888. doi:10.1007/s00454-017-9900-0"},"article_type":"original","page":"871 - 888","abstract":[{"lang":"eng","text":"We investigate the complexity of finding an embedded non-orientable surface of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into 3-manifolds. We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case."}],"issue":"4","type":"journal_article","oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"534","status":"public","title":"Finding non-orientable surfaces in 3-Manifolds","intvolume":" 58","month":"06","publication_identifier":{"issn":["01795376"]},"doi":"10.1007/s00454-017-9900-0","language":[{"iso":"eng"}],"oa":1,"external_id":{"arxiv":["1602.07907"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1602.07907"}],"quality_controlled":"1","publist_id":"7283","author":[{"full_name":"Burton, Benjamin","last_name":"Burton","first_name":"Benjamin"},{"last_name":"De Mesmay","first_name":"Arnaud N","id":"3DB2F25C-F248-11E8-B48F-1D18A9856A87","full_name":"De Mesmay, Arnaud N"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"1379"}]},"date_updated":"2023-02-21T17:01:34Z","date_created":"2018-12-11T11:47:01Z","volume":58,"year":"2017","publication_status":"published","publisher":"Springer","department":[{"_id":"UlWa"}]},{"date_published":"2017-01-01T00:00:00Z","page":"313 - 342","citation":{"apa":"Franek, P., & Krcál, M. (2017). Persistence of zero sets. Homology, Homotopy and Applications. International Press. https://doi.org/10.4310/HHA.2017.v19.n2.a16","ieee":"P. Franek and M. Krcál, “Persistence of zero sets,” Homology, Homotopy and Applications, vol. 19, no. 2. International Press, pp. 313–342, 2017.","ista":"Franek P, Krcál M. 2017. Persistence of zero sets. Homology, Homotopy and Applications. 19(2), 313–342.","ama":"Franek P, Krcál M. Persistence of zero sets. Homology, Homotopy and Applications. 2017;19(2):313-342. doi:10.4310/HHA.2017.v19.n2.a16","chicago":"Franek, Peter, and Marek Krcál. “Persistence of Zero Sets.” Homology, Homotopy and Applications. International Press, 2017. https://doi.org/10.4310/HHA.2017.v19.n2.a16.","short":"P. Franek, M. Krcál, Homology, Homotopy and Applications 19 (2017) 313–342.","mla":"Franek, Peter, and Marek Krcál. “Persistence of Zero Sets.” Homology, Homotopy and Applications, vol. 19, no. 2, International Press, 2017, pp. 313–42, doi:10.4310/HHA.2017.v19.n2.a16."},"publication":"Homology, Homotopy and Applications","day":"01","scopus_import":1,"oa_version":"Submitted Version","intvolume":" 19","title":"Persistence of zero sets","status":"public","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","_id":"568","issue":"2","abstract":[{"text":"We study robust properties of zero sets of continuous maps f: X → ℝn. Formally, we analyze the family Z< r(f) := (g-1(0): ||g - f|| < r) of all zero sets of all continuous maps g closer to f than r in the max-norm. All of these sets are outside A := (x: |f(x)| ≥ r) and we claim that Z< r(f) is fully determined by A and an element of a certain cohomotopy group which (by a recent result) is computable whenever the dimension of X is at most 2n - 3. By considering all r > 0 simultaneously, the pointed cohomotopy groups form a persistence module-a structure leading to persistence diagrams as in the case of persistent homology or well groups. Eventually, we get a descriptor of persistent robust properties of zero sets that has better descriptive power (Theorem A) and better computability status (Theorem B) than the established well diagrams. Moreover, if we endow every point of each zero set with gradients of the perturbation, the robust description of the zero sets by elements of cohomotopy groups is in some sense the best possible (Theorem C).","lang":"eng"}],"type":"journal_article","language":[{"iso":"eng"}],"doi":"10.4310/HHA.2017.v19.n2.a16","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7"},{"call_identifier":"H2020","name":"Atomic-Resolution Structures of Mitochondrial Respiratory Chain Supercomplexes (H2020)","grant_number":"701309","_id":"2590DB08-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","main_file_link":[{"url":"https://arxiv.org/abs/1507.04310","open_access":"1"}],"oa":1,"publication_identifier":{"issn":["15320073"]},"month":"01","volume":19,"date_created":"2018-12-11T11:47:14Z","date_updated":"2021-01-12T08:03:12Z","author":[{"full_name":"Franek, Peter","id":"473294AE-F248-11E8-B48F-1D18A9856A87","last_name":"Franek","first_name":"Peter"},{"id":"33E21118-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","last_name":"Krcál","full_name":"Krcál, Marek"}],"department":[{"_id":"UlWa"},{"_id":"HeEd"}],"publisher":"International Press","publication_status":"published","year":"2017","publist_id":"7246","ec_funded":1},{"abstract":[{"text":"The fact that the complete graph K5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph Kn embeds in a closed surface M (other than the Klein bottle) if and only if (n−3)(n−4) ≤ 6b1(M), where b1(M) is the first Z2-Betti number of M. On the other hand, van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of Kn+1) embeds in R2k if and only if n ≤ 2k + 1. Two decades ago, Kühnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k − 1)-connected 2k-manifold with kth Z2-Betti number bk only if the following generalized Heawood inequality holds: (k+1 n−k−1) ≤ (k+1 2k+1)bk. This is a common generalization of the case of graphs on surfaces as well as the van Kampen–Flores theorem. In the spirit of Kühnel’s conjecture, we prove that if the k-skeleton of the n-simplex embeds in a compact 2k-manifold with kth Z2-Betti number bk, then n ≤ 2bk(k 2k+2)+2k+4. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k−1)-connected. Our results generalize to maps without q-covered points, in the spirit of Tverberg’s theorem, for q a prime power. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.","lang":"eng"}],"issue":"2","type":"journal_article","oa_version":"Preprint","status":"public","title":"On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result","intvolume":" 222","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"610","day":"01","scopus_import":1,"date_published":"2017-10-01T00:00:00Z","page":"841 - 866","publication":"Israel Journal of Mathematics","citation":{"apa":"Goaoc, X., Mabillard, I., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2017). On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result. Israel Journal of Mathematics. Springer. https://doi.org/10.1007/s11856-017-1607-7","ieee":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result,” Israel Journal of Mathematics, vol. 222, no. 2. Springer, pp. 841–866, 2017.","ista":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. 2017. On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result. Israel Journal of Mathematics. 222(2), 841–866.","ama":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result. Israel Journal of Mathematics. 2017;222(2):841-866. doi:10.1007/s11856-017-1607-7","chicago":"Goaoc, Xavier, Isaac Mabillard, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “On Generalized Heawood Inequalities for Manifolds: A van Kampen–Flores Type Nonembeddability Result.” Israel Journal of Mathematics. Springer, 2017. https://doi.org/10.1007/s11856-017-1607-7.","short":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, U. Wagner, Israel Journal of Mathematics 222 (2017) 841–866.","mla":"Goaoc, Xavier, et al. “On Generalized Heawood Inequalities for Manifolds: A van Kampen–Flores Type Nonembeddability Result.” Israel Journal of Mathematics, vol. 222, no. 2, Springer, 2017, pp. 841–66, doi:10.1007/s11856-017-1607-7."},"ec_funded":1,"publist_id":"7194","date_created":"2018-12-11T11:47:29Z","date_updated":"2023-02-23T10:02:13Z","volume":222,"author":[{"first_name":"Xavier","last_name":"Goaoc","full_name":"Goaoc, Xavier"},{"full_name":"Mabillard, Isaac","first_name":"Isaac","last_name":"Mabillard","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Paták, Pavel","first_name":"Pavel","last_name":"Paták"},{"last_name":"Patakova","first_name":"Zuzana","orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87","full_name":"Patakova, Zuzana"},{"last_name":"Tancer","first_name":"Martin","orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","full_name":"Tancer, Martin"},{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"}],"related_material":{"record":[{"id":"1511","relation":"earlier_version","status":"public"}]},"publication_status":"published","publisher":"Springer","department":[{"_id":"UlWa"}],"year":"2017","acknowledgement":"The work by Z. P. was partially supported by the Israel Science Foundation grant ISF-768/12. The work by Z. P. and M. T. was partially supported by the project CE-ITI (GACR P202/12/G061) of the Czech Science Foundation and by the ERC Advanced Grant No. 267165. Part of the research work of M.T. was conducted at IST Austria, supported by an IST Fellowship. The research of P. P. was supported by the ERC Advanced grant no. 320924. The work by I. M. and U. W. was supported by the Swiss National Science Foundation (grants SNSF-200020-138230 and SNSF-PP00P2-138948). The collaboration between U. W. and X. G. was partially supported by the LabEx Bézout (ANR-10-LABX-58).","month":"10","language":[{"iso":"eng"}],"doi":"10.1007/s11856-017-1607-7","quality_controlled":"1","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1610.09063","open_access":"1"}]},{"month":"12","doi":"10.4230/LIPICS.ISAAC.2017.34","conference":{"location":"Phuket, Thailand","start_date":"2017-12-09","end_date":"2017-12-22","name":"ISAAC: International Symposium on Algorithms and Computation"},"language":[{"iso":"eng"}],"tmp":{"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)","image":"/images/cc_by.png"},"oa":1,"project":[{"call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281"}],"quality_controlled":"1","ec_funded":1,"file_date_updated":"2020-07-14T12:47:33Z","article_number":"34","author":[{"full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","first_name":"Radoslav"}],"volume":92,"date_created":"2019-06-04T12:11:52Z","date_updated":"2021-01-12T08:07:51Z","year":"2017","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","has_accepted_license":"1","day":"01","scopus_import":1,"date_published":"2017-12-01T00:00:00Z","citation":{"chicago":"Fulek, Radoslav. “Embedding Graphs into Embedded Graphs,” Vol. 92. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ISAAC.2017.34.","mla":"Fulek, Radoslav. Embedding Graphs into Embedded Graphs. Vol. 92, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ISAAC.2017.34.","short":"R. Fulek, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ista":"Fulek R. 2017. Embedding graphs into embedded graphs. ISAAC: International Symposium on Algorithms and Computation vol. 92, 34.","apa":"Fulek, R. (2017). Embedding graphs into embedded graphs (Vol. 92). Presented at the ISAAC: International Symposium on Algorithms and Computation, Phuket, Thailand: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ISAAC.2017.34","ieee":"R. Fulek, “Embedding graphs into embedded graphs,” presented at the ISAAC: International Symposium on Algorithms and Computation, Phuket, Thailand, 2017, vol. 92.","ama":"Fulek R. Embedding graphs into embedded graphs. In: Vol 92. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ISAAC.2017.34"},"abstract":[{"lang":"eng","text":"A (possibly degenerate) drawing of a graph G in the plane is approximable by an embedding if it can be turned into an embedding by an arbitrarily small perturbation. We show that testing, whether a drawing of a planar graph G in the plane is approximable by an embedding, can be carried out in polynomial time, if a desired embedding of G belongs to a fixed isotopy class, i.e., the rotation system (or equivalently the faces) of the embedding of G and the choice of outer face are fixed. In other words, we show that c-planarity with embedded pipes is tractable for graphs with fixed embeddings. To the best of our knowledge an analogous result was previously known essentially only when G is a cycle."}],"type":"conference","oa_version":"Published Version","file":[{"checksum":"fc7a643e29621c8bbe49d36b39081f31","date_updated":"2020-07-14T12:47:33Z","date_created":"2019-06-04T12:20:35Z","file_id":"6518","relation":"main_file","creator":"kschuh","file_size":588982,"content_type":"application/pdf","access_level":"open_access","file_name":"2017_LIPIcs-Fulek.pdf"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"6517","intvolume":" 92","status":"public","ddc":["510"],"title":"Embedding graphs into embedded graphs"},{"file":[{"checksum":"067ab0cb3f962bae6c3af6bf0094e0f3","date_created":"2018-12-12T10:11:03Z","date_updated":"2020-07-14T12:47:42Z","file_id":"4856","relation":"main_file","creator":"system","file_size":990546,"content_type":"application/pdf","access_level":"open_access","file_name":"IST-2017-895-v1+1_LIPIcs-SoCG-2017-39.pdf"}],"oa_version":"Published Version","pubrep_id":"895","ddc":["514","516"],"status":"public","title":"Topological data analysis with Bregman divergences","intvolume":" 77","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"688","abstract":[{"lang":"eng","text":"We show that the framework of topological data analysis can be extended from metrics to general Bregman divergences, widening the scope of possible applications. Examples are the Kullback - Leibler divergence, which is commonly used for comparing text and images, and the Itakura - Saito divergence, popular for speech and sound. In particular, we prove that appropriately generalized čech and Delaunay (alpha) complexes capture the correct homotopy type, namely that of the corresponding union of Bregman balls. Consequently, their filtrations give the correct persistence diagram, namely the one generated by the uniformly growing Bregman balls. Moreover, we show that unlike the metric setting, the filtration of Vietoris-Rips complexes may fail to approximate the persistence diagram. We propose algorithms to compute the thus generalized čech, Vietoris-Rips and Delaunay complexes and experimentally test their efficiency. Lastly, we explain their surprisingly good performance by making a connection with discrete Morse theory. "}],"alternative_title":["LIPIcs"],"type":"conference","date_published":"2017-06-01T00:00:00Z","page":"391-3916","citation":{"short":"H. Edelsbrunner, H. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 391–3916.","mla":"Edelsbrunner, Herbert, and Hubert Wagner. Topological Data Analysis with Bregman Divergences. Vol. 77, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 391–3916, doi:10.4230/LIPIcs.SoCG.2017.39.","chicago":"Edelsbrunner, Herbert, and Hubert Wagner. “Topological Data Analysis with Bregman Divergences,” 77:391–3916. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.SoCG.2017.39.","ama":"Edelsbrunner H, Wagner H. Topological data analysis with Bregman divergences. In: Vol 77. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017:391-3916. doi:10.4230/LIPIcs.SoCG.2017.39","apa":"Edelsbrunner, H., & Wagner, H. (2017). Topological data analysis with Bregman divergences (Vol. 77, pp. 391–3916). Presented at the Symposium on Computational Geometry, SoCG, Brisbane, Australia: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2017.39","ieee":"H. Edelsbrunner and H. Wagner, “Topological data analysis with Bregman divergences,” presented at the Symposium on Computational Geometry, SoCG, Brisbane, Australia, 2017, vol. 77, pp. 391–3916.","ista":"Edelsbrunner H, Wagner H. 2017. Topological data analysis with Bregman divergences. Symposium on Computational Geometry, SoCG, LIPIcs, vol. 77, 391–3916."},"day":"01","has_accepted_license":"1","scopus_import":1,"date_created":"2018-12-11T11:47:56Z","date_updated":"2021-01-12T08:09:26Z","volume":77,"author":[{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"},{"last_name":"Wagner","first_name":"Hubert","id":"379CA8B8-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Hubert"}],"publication_status":"published","department":[{"_id":"HeEd"},{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2017","file_date_updated":"2020-07-14T12:47:42Z","publist_id":"7021","language":[{"iso":"eng"}],"conference":{"end_date":"2017-07-07","start_date":"2017-07-04","location":"Brisbane, Australia","name":"Symposium on Computational Geometry, SoCG"},"doi":"10.4230/LIPIcs.SoCG.2017.39","quality_controlled":"1","oa":1,"tmp":{"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)","image":"/images/cc_by.png"},"month":"06","publication_identifier":{"issn":["18688969"]}},{"file":[{"relation":"main_file","file_id":"5077","checksum":"a431e573e31df13bc0f66de3061006ec","date_updated":"2020-07-14T12:47:47Z","date_created":"2018-12-12T10:14:25Z","access_level":"open_access","file_name":"IST-2018-984-v1+1_Patakova_on_the_nonexistence_of_k-reptile_simplices_in_R_3_and_R_4_2017.pdf","file_size":544042,"content_type":"application/pdf","creator":"system"}],"oa_version":"Submitted Version","pubrep_id":"984","intvolume":" 24","title":"On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4","status":"public","ddc":["500"],"_id":"701","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"3","abstract":[{"lang":"eng","text":"A d-dimensional simplex S is called a k-reptile (or a k-reptile simplex) if it can be tiled by k simplices with disjoint interiors that are all mutually congruent and similar to S. For d = 2, triangular k-reptiles exist for all k of the form a^2, 3a^2 or a^2+b^2 and they have been completely characterized by Snover, Waiveris, and Williams. On the other hand, the only k-reptile simplices that are known for d ≥ 3, have k = m^d, where m is a positive integer. We substantially simplify the proof by Matoušek and the second author that for d = 3, k-reptile tetrahedra can exist only for k = m^3. We then prove a weaker analogue of this result for d = 4 by showing that four-dimensional k-reptile simplices can exist only for k = m^2."}],"type":"journal_article","date_published":"2017-07-14T00:00:00Z","page":"1-44","citation":{"chicago":"Kynčl, Jan, and Zuzana Patakova. “On the Nonexistence of k Reptile Simplices in ℝ^3 and ℝ^4.” The Electronic Journal of Combinatorics. International Press, 2017.","short":"J. Kynčl, Z. Patakova, The Electronic Journal of Combinatorics 24 (2017) 1–44.","mla":"Kynčl, Jan, and Zuzana Patakova. “On the Nonexistence of k Reptile Simplices in ℝ^3 and ℝ^4.” The Electronic Journal of Combinatorics, vol. 24, no. 3, International Press, 2017, pp. 1–44.","ieee":"J. Kynčl and Z. Patakova, “On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4,” The Electronic Journal of Combinatorics, vol. 24, no. 3. International Press, pp. 1–44, 2017.","apa":"Kynčl, J., & Patakova, Z. (2017). On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4. The Electronic Journal of Combinatorics. International Press.","ista":"Kynčl J, Patakova Z. 2017. On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4. The Electronic Journal of Combinatorics. 24(3), 1–44.","ama":"Kynčl J, Patakova Z. On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4. The Electronic Journal of Combinatorics. 2017;24(3):1-44."},"publication":"The Electronic Journal of Combinatorics","has_accepted_license":"1","day":"14","volume":24,"date_created":"2018-12-11T11:48:00Z","date_updated":"2021-01-12T08:11:28Z","author":[{"first_name":"Jan","last_name":"Kynčl","full_name":"Kynčl, Jan"},{"first_name":"Zuzana","last_name":"Patakova","id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683","full_name":"Patakova, Zuzana"}],"publisher":"International Press","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2017","publist_id":"6996","file_date_updated":"2020-07-14T12:47:47Z","language":[{"iso":"eng"}],"quality_controlled":"1","oa":1,"publication_identifier":{"issn":["10778926"]},"month":"07"},{"oa":1,"project":[{"call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","doi":"10.37236/6663","language":[{"iso":"eng"}],"publication_identifier":{"issn":["10778926"]},"month":"07","year":"2017","publisher":"International Press","department":[{"_id":"UlWa"}],"publication_status":"published","author":[{"last_name":"Fulek","first_name":"Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav"},{"full_name":"Kynčl, Jan","last_name":"Kynčl","first_name":"Jan"},{"full_name":"Pálvölgyi, Dömötör","first_name":"Dömötör","last_name":"Pálvölgyi"}],"volume":24,"date_created":"2018-12-11T11:48:32Z","date_updated":"2022-03-18T12:58:53Z","article_number":"P3.18","ec_funded":1,"publist_id":"6859","file_date_updated":"2020-07-14T12:48:06Z","citation":{"ista":"Fulek R, Kynčl J, Pálvölgyi D. 2017. Unified Hanani Tutte theorem. Electronic Journal of Combinatorics. 24(3), P3.18.","apa":"Fulek, R., Kynčl, J., & Pálvölgyi, D. (2017). Unified Hanani Tutte theorem. Electronic Journal of Combinatorics. International Press. https://doi.org/10.37236/6663","ieee":"R. Fulek, J. Kynčl, and D. Pálvölgyi, “Unified Hanani Tutte theorem,” Electronic Journal of Combinatorics, vol. 24, no. 3. International Press, 2017.","ama":"Fulek R, Kynčl J, Pálvölgyi D. Unified Hanani Tutte theorem. Electronic Journal of Combinatorics. 2017;24(3). doi:10.37236/6663","chicago":"Fulek, Radoslav, Jan Kynčl, and Dömötör Pálvölgyi. “Unified Hanani Tutte Theorem.” Electronic Journal of Combinatorics. International Press, 2017. https://doi.org/10.37236/6663.","mla":"Fulek, Radoslav, et al. “Unified Hanani Tutte Theorem.” Electronic Journal of Combinatorics, vol. 24, no. 3, P3.18, International Press, 2017, doi:10.37236/6663.","short":"R. Fulek, J. Kynčl, D. Pálvölgyi, Electronic Journal of Combinatorics 24 (2017)."},"publication":"Electronic Journal of Combinatorics","article_type":"original","date_published":"2017-07-28T00:00:00Z","scopus_import":"1","article_processing_charge":"No","has_accepted_license":"1","day":"28","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"795","intvolume":" 24","title":"Unified Hanani Tutte theorem","status":"public","ddc":["000"],"oa_version":"Published Version","file":[{"file_name":"2017_ElectrCombi_Fulek.pdf","access_level":"open_access","creator":"dernst","content_type":"application/pdf","file_size":236944,"file_id":"5853","relation":"main_file","date_updated":"2020-07-14T12:48:06Z","date_created":"2019-01-18T14:04:08Z","checksum":"ef320cff0f062051e858f929be6a3581"}],"type":"journal_article","issue":"3","abstract":[{"lang":"eng","text":"We introduce a common generalization of the strong Hanani–Tutte theorem and the weak Hanani–Tutte theorem: if a graph G has a drawing D in the plane where every pair of independent edges crosses an even number of times, then G has a planar drawing preserving the rotation of each vertex whose incident edges cross each other evenly in D. The theorem is implicit in the proof of the strong Hanani–Tutte theorem by Pelsmajer, Schaefer and Štefankovič. We give a new, somewhat simpler proof."}]},{"article_number":"49","file_date_updated":"2020-07-14T12:47:41Z","publist_id":"7033","publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"year":"2017","date_created":"2018-12-11T11:47:54Z","date_updated":"2023-09-05T15:01:43Z","volume":77,"author":[{"full_name":"Lubiw, Anna","first_name":"Anna","last_name":"Lubiw"},{"last_name":"Masárová","first_name":"Zuzana","orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","full_name":"Masárová, Zuzana"},{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"}],"related_material":{"record":[{"status":"public","relation":"later_version","id":"5986"}]},"month":"06","quality_controlled":"1","tmp":{"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)","image":"/images/cc_by.png"},"oa":1,"language":[{"iso":"eng"}],"conference":{"location":"Brisbane, Australia","start_date":"2017-07-04","end_date":"2017-07-07","name":"SoCG: Symposium on Computational Geometry"},"doi":"10.4230/LIPIcs.SoCG.2017.49","alternative_title":["LIPIcs"],"type":"conference","abstract":[{"lang":"eng","text":"Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of O(n7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture."}],"ddc":["514","516"],"title":"A proof of the orbit conjecture for flipping edge labelled triangulations","status":"public","intvolume":" 77","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"683","file":[{"file_name":"IST-2017-896-v1+1_LIPIcs-SoCG-2017-49.pdf","access_level":"open_access","file_size":710007,"content_type":"application/pdf","creator":"system","relation":"main_file","file_id":"5265","date_created":"2018-12-12T10:17:12Z","date_updated":"2020-07-14T12:47:41Z","checksum":"24fdde981cc513352a78dcf9b0660ae9"}],"oa_version":"Published Version","pubrep_id":"896","scopus_import":1,"day":"01","has_accepted_license":"1","citation":{"ista":"Lubiw A, Masárová Z, Wagner U. 2017. A proof of the orbit conjecture for flipping edge labelled triangulations. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 77, 49.","ieee":"A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for flipping edge labelled triangulations,” presented at the SoCG: Symposium on Computational Geometry, Brisbane, Australia, 2017, vol. 77.","apa":"Lubiw, A., Masárová, Z., & Wagner, U. (2017). A proof of the orbit conjecture for flipping edge labelled triangulations (Vol. 77). Presented at the SoCG: Symposium on Computational Geometry, Brisbane, Australia: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2017.49","ama":"Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping edge labelled triangulations. In: Vol 77. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.SoCG.2017.49","chicago":"Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture for Flipping Edge Labelled Triangulations,” Vol. 77. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.SoCG.2017.49.","mla":"Lubiw, Anna, et al. A Proof of the Orbit Conjecture for Flipping Edge Labelled Triangulations. Vol. 77, 49, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.SoCG.2017.49.","short":"A. Lubiw, Z. Masárová, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017."},"date_published":"2017-06-01T00:00:00Z"},{"title":"Algorithmic solvability of the lifting extension problem","status":"public","intvolume":" 54","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"1073","oa_version":"Submitted Version","type":"journal_article","abstract":[{"text":"Let X and Y be finite simplicial sets (e.g. finite simplicial complexes), both equipped with a free simplicial action of a finite group G. Assuming that Y is d-connected and dimX≤2d, for some d≥1, we provide an algorithm that computes the set of all equivariant homotopy classes of equivariant continuous maps |X|→|Y|; the existence of such a map can be decided even for dimX≤2d+1. This yields the first algorithm for deciding topological embeddability of a k-dimensional finite simplicial complex into Rn under the condition k≤23n−1. More generally, we present an algorithm that, given a lifting-extension problem satisfying an appropriate stability assumption, computes the set of all homotopy classes of solutions. This result is new even in the non-equivariant situation.","lang":"eng"}],"issue":"4","page":"915 - 965","publication":"Discrete & Computational Geometry","citation":{"ama":"Čadek M, Krcál M, Vokřínek L. Algorithmic solvability of the lifting extension problem. Discrete & Computational Geometry. 2017;54(4):915-965. doi:10.1007/s00454-016-9855-6","ista":"Čadek M, Krcál M, Vokřínek L. 2017. Algorithmic solvability of the lifting extension problem. Discrete & Computational Geometry. 54(4), 915–965.","ieee":"M. Čadek, M. Krcál, and L. Vokřínek, “Algorithmic solvability of the lifting extension problem,” Discrete & Computational Geometry, vol. 54, no. 4. Springer, pp. 915–965, 2017.","apa":"Čadek, M., Krcál, M., & Vokřínek, L. (2017). Algorithmic solvability of the lifting extension problem. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-016-9855-6","mla":"Čadek, Martin, et al. “Algorithmic Solvability of the Lifting Extension Problem.” Discrete & Computational Geometry, vol. 54, no. 4, Springer, 2017, pp. 915–65, doi:10.1007/s00454-016-9855-6.","short":"M. Čadek, M. Krcál, L. Vokřínek, Discrete & Computational Geometry 54 (2017) 915–965.","chicago":"Čadek, Martin, Marek Krcál, and Lukáš Vokřínek. “Algorithmic Solvability of the Lifting Extension Problem.” Discrete & Computational Geometry. Springer, 2017. https://doi.org/10.1007/s00454-016-9855-6."},"date_published":"2017-06-01T00:00:00Z","scopus_import":"1","day":"01","article_processing_charge":"No","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Springer","year":"2017","date_created":"2018-12-11T11:50:00Z","date_updated":"2023-09-20T12:01:28Z","volume":54,"author":[{"full_name":"Čadek, Martin","last_name":"Čadek","first_name":"Martin"},{"id":"33E21118-F248-11E8-B48F-1D18A9856A87","last_name":"Krcál","first_name":"Marek","full_name":"Krcál, Marek"},{"first_name":"Lukáš","last_name":"Vokřínek","full_name":"Vokřínek, Lukáš"}],"publist_id":"6309","isi":1,"quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1307.6444"}],"external_id":{"isi":["000400072700008"]},"oa":1,"language":[{"iso":"eng"}],"doi":"10.1007/s00454-016-9855-6","month":"06","publication_identifier":{"issn":["01795376"]}}]