[{"volume":164,"external_id":{"arxiv":["1908.01677"]},"file_date_updated":"2020-07-14T12:48:06Z","intvolume":" 164","citation":{"apa":"Patakova, Z. (2020). Bounding radon number via Betti numbers. In *36th International Symposium on Computational Geometry* (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.61","short":"Z. Patakova, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","mla":"Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” *36th International Symposium on Computational Geometry*, vol. 164, 61:1-61:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.61.","ieee":"Z. Patakova, “Bounding radon number via Betti numbers,” in *36th International Symposium on Computational Geometry*, Zürich, Switzerland, 2020, vol. 164.","ista":"Patakova Z. 2020. Bounding radon number via Betti numbers. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164.","ama":"Patakova Z. Bounding radon number via Betti numbers. In: *36th International Symposium on Computational Geometry*. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.61","chicago":"Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” In *36th International Symposium on Computational Geometry*, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.61."},"title":"Bounding radon number via Betti numbers","date_updated":"2020-11-17T14:02:08Z","month":"06","ddc":["510"],"date_created":"2020-06-22T09:14:18Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","alternative_title":["LIPIcs"],"status":"public","year":"2020","article_number":"61:1-61:13","article_processing_charge":"No","quality_controlled":"1","author":[{"id":"48B57058-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","last_name":"Patakova","full_name":"Patakova, Zuzana","orcid":"0000-0002-3975-1683"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"doi":"10.4230/LIPIcs.SoCG.2020.61","abstract":[{"text":"We prove general topological Radon-type theorems for sets in ℝ^d, smooth real manifolds or finite dimensional simplicial complexes. Combined with a recent result of Holmsen and Lee, it gives fractional Helly theorem, and consequently the existence of weak ε-nets as well as a (p,q)-theorem. More precisely: Let X be either ℝ^d, smooth real d-manifold, or a finite d-dimensional simplicial complex. Then if F is a finite, intersection-closed family of sets in X such that the ith reduced Betti number (with ℤ₂ coefficients) of any set in F is at most b for every non-negative integer i less or equal to k, then the Radon number of F is bounded in terms of b and X. Here k is the smallest integer larger or equal to d/2 - 1 if X = ℝ^d; k=d-1 if X is a smooth real d-manifold and not a surface, k=0 if X is a surface and k=d if X is a d-dimensional simplicial complex. Using the recent result of the author and Kalai, we manage to prove the following optimal bound on fractional Helly number for families of open sets in a surface: Let F be a finite family of open sets in a surface S such that the intersection of any subfamily of F is either empty, or path-connected. Then the fractional Helly number of F is at most three. This also settles a conjecture of Holmsen, Kim, and Lee about an existence of a (p,q)-theorem for open subsets of a surface.","lang":"eng"}],"file":[{"access_level":"open_access","file_size":645421,"checksum":"d0996ca5f6eb32ce955ce782b4f2afbe","relation":"main_file","creator":"dernst","content_type":"application/pdf","file_name":"2020_LIPIcsSoCG_Patakova_61.pdf","date_updated":"2020-07-14T12:48:06Z","date_created":"2020-06-23T06:56:23Z","file_id":"8005"}],"license":"https://creativecommons.org/licenses/by/4.0/","language":[{"iso":"eng"}],"type":"conference","has_accepted_license":"1","day":"01","scopus_import":"1","_id":"7989","department":[{"_id":"UlWa"}],"oa_version":"Published Version","date_published":"2020-06-01T00:00:00Z","oa":1,"publication":"36th International Symposium on Computational Geometry","publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"conference":{"start_date":"2020-06-22","end_date":"2020-06-26","location":"Zürich, Switzerland","name":"SoCG: Symposium on Computational Geometry"}},{"author":[{"full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","last_name":"Masárová","first_name":"Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87"}],"article_processing_charge":"No","status":"public","year":"2020","tmp":{"short":"CC BY-SA (4.0)","legal_code_url":"https://creativecommons.org/licenses/by-sa/4.0/legalcode","name":"Creative Commons Attribution-ShareAlike 4.0 International Public License (CC BY-SA 4.0)","image":"/images/cc_by_sa.png"},"abstract":[{"lang":"eng","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."}],"doi":"10.15479/AT:ISTA:7944","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"id":"5986","relation":"part_of_dissertation","status":"public"},{"status":"public","relation":"part_of_dissertation","id":"7950"}]},"publication_status":"published","month":"06","date_created":"2020-06-08T00:49:46Z","ddc":["516","514"],"citation":{"mla":"Masárová, Zuzana. *Reconfiguration Problems*. IST Austria, 2020, doi:10.15479/AT:ISTA:7944.","ieee":"Z. Masárová, *Reconfiguration problems*. IST Austria, 2020.","short":"Z. Masárová, Reconfiguration Problems, IST Austria, 2020.","apa":"Masárová, Z. (2020). *Reconfiguration problems*. IST Austria. https://doi.org/10.15479/AT:ISTA:7944","chicago":"Masárová, Zuzana. *Reconfiguration Problems*. IST Austria, 2020. https://doi.org/10.15479/AT:ISTA:7944.","ista":"Masárová Z. 2020. Reconfiguration problems, IST Austria, 160p.","ama":"Masárová Z. *Reconfiguration Problems*. IST Austria; 2020. doi:10.15479/AT:ISTA:7944"},"title":"Reconfiguration problems","date_updated":"2020-11-25T09:28:51Z","file_date_updated":"2020-07-14T12:48:05Z","alternative_title":["IST Austria Thesis"],"publisher":"IST Austria","oa":1,"date_published":"2020-06-09T00:00:00Z","oa_version":"Published Version","publication_identifier":{"eissn":["2663-337X"],"isbn":["978-3-99078-005-3"]},"has_accepted_license":"1","language":[{"iso":"eng"}],"type":"dissertation","file":[{"file_size":13661779,"access_level":"open_access","creator":"zmasarov","content_type":"application/pdf","checksum":"df688bc5a82b50baee0b99d25fc7b7f0","relation":"main_file","file_id":"7945","date_created":"2020-06-08T00:34:00Z","file_name":"THESIS_Zuzka_Masarova.pdf","date_updated":"2020-07-14T12:48:05Z"},{"file_size":32184006,"access_level":"closed","creator":"zmasarov","content_type":"application/zip","checksum":"45341a35b8f5529c74010b7af43ac188","relation":"source_file","date_created":"2020-06-08T00:35:30Z","file_id":"7946","file_name":"THESIS_Zuzka_Masarova_SOURCE_FILES.zip","date_updated":"2020-07-14T12:48:05Z"}],"license":"https://creativecommons.org/licenses/by-sa/4.0/","page":"160","_id":"7944","department":[{"_id":"HeEd"},{"_id":"UlWa"}],"supervisor":[{"orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"keyword":["reconfiguration","reconfiguration graph","triangulations","flip","constrained triangulations","shellability","piecewise-linear balls","token swapping","trees","coloured weighted token swapping"],"day":"09"},{"external_id":{"arxiv":["1907.00885"]},"volume":64,"month":"09","date_created":"2020-06-14T22:00:50Z","intvolume":" 64","citation":{"short":"G. Kalai, Z. Patakova, Discrete and Computational Geometry 64 (2020) 304–323.","apa":"Kalai, G., & Patakova, Z. (2020). Intersection patterns of planar sets. *Discrete and Computational Geometry*, *64*, 304–323. 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, pp. 304–323, 2020.","mla":"Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.” *Discrete and Computational Geometry*, vol. 64, Springer Nature, 2020, pp. 304–23, doi:10.1007/s00454-020-00205-z.","ista":"Kalai G, Patakova Z. 2020. Intersection patterns of planar sets. Discrete and Computational Geometry. 64, 304–323.","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* 64 (2020): 304–23. https://doi.org/10.1007/s00454-020-00205-z."},"title":"Intersection patterns of planar sets","date_updated":"2020-11-25T09:53:28Z","publisher":"Springer Nature","article_processing_charge":"No","quality_controlled":"1","year":"2020","status":"public","author":[{"first_name":"Gil","last_name":"Kalai","full_name":"Kalai, Gil"},{"last_name":"Patakova","orcid":"0000-0002-3975-1683","full_name":"Patakova, Zuzana","id":"48B57058-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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.","abstract":[{"lang":"eng","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."}],"doi":"10.1007/s00454-020-00205-z","page":"304-323","type":"journal_article","language":[{"iso":"eng"}],"day":"01","department":[{"_id":"UlWa"}],"_id":"7960","scopus_import":"1","article_type":"original","oa_version":"Preprint","oa":1,"publication":"Discrete and Computational Geometry","date_published":"2020-09-01T00:00:00Z","publication_identifier":{"issn":["01795376"],"eissn":["14320444"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1907.00885"}]},{"publisher":"Springer Nature","alternative_title":["LNCS"],"external_id":{"arxiv":["1908.08129"]},"volume":11904,"date_created":"2020-01-05T23:00:47Z","month":"11","title":"Extending simple drawings","citation":{"short":"A.M. Arroyo Guevara, M. Derka, I. Parada, in:, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Nature, 2019, pp. 230–243.","apa":"Arroyo Guevara, A. M., Derka, M., & Parada, I. (2019). Extending simple drawings. In *Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)* (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 *Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*, Prague, Czech Republic, 2019, vol. 11904, pp. 230–243.","mla":"Arroyo Guevara, Alan M., et al. “Extending Simple Drawings.” *Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*, vol. 11904, Springer Nature, 2019, pp. 230–43, doi:10.1007/978-3-030-35802-0_18.","ista":"Arroyo Guevara AM, Derka M, Parada I. 2019. Extending simple drawings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). GD: Graph Drawing and Network Visualization, LNCS, vol. 11904. 230–243.","ama":"Arroyo Guevara AM, Derka M, Parada I. Extending simple drawings. In: *Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*. Vol 11904. Springer Nature; 2019:230-243. doi:10.1007/978-3-030-35802-0_18","chicago":"Arroyo Guevara, Alan M, Martin Derka, and Irene Parada. “Extending Simple Drawings.” In *Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*, 11904:230–43. Springer Nature, 2019. https://doi.org/10.1007/978-3-030-35802-0_18."},"date_updated":"2020-08-11T10:10:50Z","intvolume":" 11904","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","abstract":[{"lang":"eng","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."}],"doi":"10.1007/978-3-030-35802-0_18","quality_controlled":"1","article_processing_charge":"No","year":"2019","status":"public","author":[{"id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","first_name":"Alan M","last_name":"Arroyo Guevara","full_name":"Arroyo Guevara, Alan M"},{"last_name":"Derka","full_name":"Derka, Martin","first_name":"Martin"},{"first_name":"Irene","last_name":"Parada","full_name":"Parada, Irene"}],"day":"28","_id":"7230","department":[{"_id":"UlWa"}],"scopus_import":1,"page":"230-243","type":"conference","language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9783030358013"],"issn":["03029743"],"eissn":["16113349"]},"main_file_link":[{"url":"https://arxiv.org/abs/1908.08129","open_access":"1"}],"conference":{"location":"Prague, Czech Republic","name":"GD: Graph Drawing and Network Visualization","start_date":"2019-09-17","end_date":"2019-09-20"},"project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"}],"oa_version":"Preprint","publication":"Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)","oa":1,"ec_funded":1,"date_published":"2019-11-28T00:00:00Z"},{"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","alternative_title":["LIPIcs"],"volume":129,"external_id":{"arxiv":["1903.08637"]},"file_date_updated":"2020-07-14T12:47:57Z","intvolume":" 129","date_updated":"2020-08-11T10:10:51Z","citation":{"short":"R. Fulek, J. Kyncl, in:, 35th International Symposium on Computational Geometry (SoCG 2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.","apa":"Fulek, R., & Kyncl, J. (2019). Z_2-Genus of graphs and minimum rank of partial symmetric matrices. In *35th International Symposium on Computational Geometry (SoCG 2019)* (Vol. 129). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.39","mla":"Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices.” *35th International Symposium on Computational Geometry (SoCG 2019)*, vol. 129, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.SOCG.2019.39.","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.","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.","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","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."},"title":"Z_2-Genus of graphs and minimum rank of partial symmetric matrices","month":"06","date_created":"2020-01-29T16:17:05Z","ddc":["000"],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"doi":"10.4230/LIPICS.SOCG.2019.39","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. "}],"status":"public","year":"2019","article_number":"39","article_processing_charge":"No","quality_controlled":"1","author":[{"full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Jan","full_name":"Kyncl, Jan","last_name":"Kyncl"}],"day":"01","scopus_import":1,"_id":"7401","department":[{"_id":"UlWa"}],"file":[{"date_created":"2020-02-04T09:14:31Z","file_id":"7445","file_name":"2019_LIPIcs_Fulek.pdf","date_updated":"2020-07-14T12:47:57Z","file_size":628347,"access_level":"open_access","creator":"dernst","content_type":"application/pdf","checksum":"aac37b09118cc0ab58cf77129e691f8c","relation":"main_file"}],"has_accepted_license":"1","language":[{"iso":"eng"}],"type":"conference","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-104-7"]},"project":[{"name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281"}],"conference":{"start_date":"2019-06-18","end_date":"2019-06-21","name":"SoCG: Symposium on Computational Geometry","location":"Portland, OR, United States"},"oa_version":"Published Version","date_published":"2019-06-01T00:00:00Z","oa":1,"publication":"35th International Symposium on Computational Geometry (SoCG 2019)"},{"author":[{"first_name":"Steven","full_name":"Chaplick, Steven","last_name":"Chaplick"},{"last_name":"Fulek","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav"},{"last_name":"Klavík","full_name":"Klavík, Pavel","first_name":"Pavel"}],"status":"public","year":"2019","article_processing_charge":"No","quality_controlled":"1","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"}],"doi":"10.1002/jgt.22436","publication_status":"published","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","intvolume":" 91","date_updated":"2020-08-11T10:10:24Z","citation":{"ieee":"S. Chaplick, R. Fulek, and P. Klavík, “Extending partial representations of circle graphs,” *Journal of Graph Theory*, vol. 91, no. 4, 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.","apa":"Chaplick, S., Fulek, R., & Klavík, P. (2019). Extending partial representations of circle graphs. *Journal of Graph Theory*, *91*(4), 365–394. https://doi.org/10.1002/jgt.22436","chicago":"Chaplick, Steven, Radoslav Fulek, and Pavel Klavík. “Extending Partial Representations of Circle Graphs.” *Journal of Graph Theory* 91, no. 4 (2019): 365–94. https://doi.org/10.1002/jgt.22436.","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."},"title":"Extending partial representations of circle graphs","month":"08","date_created":"2018-12-30T22:59:15Z","volume":91,"external_id":{"arxiv":["1309.2399"]},"publisher":"Wiley","date_published":"2019-08-01T00:00:00Z","oa":1,"ec_funded":1,"publication":"Journal of Graph Theory","oa_version":"Preprint","article_type":"original","project":[{"name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1309.2399"}],"publication_identifier":{"issn":["03649024"]},"type":"journal_article","language":[{"iso":"eng"}],"page":"365-394","issue":"4","scopus_import":1,"department":[{"_id":"UlWa"}],"_id":"5790","day":"01"},{"oa_version":"Preprint","article_type":"original","date_published":"2019-04-30T00:00:00Z","publication":"Discrete Applied Mathematics","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1708.08037","open_access":"1"}],"publication_identifier":{"issn":["0166218X"]},"project":[{"name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","call_identifier":"FWF"}],"issue":"4","page":"266-231","type":"journal_article","language":[{"iso":"eng"}],"day":"30","scopus_import":1,"_id":"5857","department":[{"_id":"UlWa"}],"status":"public","year":"2019","quality_controlled":"1","article_processing_charge":"No","author":[{"orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pach","full_name":"Pach, János","first_name":"János"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"id":"433","relation":"earlier_version","status":"public"}]},"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."}],"doi":"10.1016/j.dam.2018.12.025","volume":259,"external_id":{"arxiv":["1708.08037"]},"date_updated":"2020-08-11T10:10:25Z","title":"Thrackles: An improved upper bound","citation":{"ista":"Fulek R, Pach J. 2019. Thrackles: An improved upper bound. Discrete Applied Mathematics. 259(4), 266–231.","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","chicago":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” *Discrete Applied Mathematics* 259, no. 4 (2019): 266–231. https://doi.org/10.1016/j.dam.2018.12.025.","apa":"Fulek, R., & Pach, J. (2019). Thrackles: An improved upper bound. *Discrete Applied Mathematics*, *259*(4), 266–231. https://doi.org/10.1016/j.dam.2018.12.025","short":"R. Fulek, J. Pach, Discrete Applied Mathematics 259 (2019) 266–231.","ieee":"R. Fulek and J. Pach, “Thrackles: An improved upper bound,” *Discrete Applied Mathematics*, vol. 259, no. 4, pp. 266–231, 2019.","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."},"intvolume":" 259","date_created":"2019-01-20T22:59:17Z","month":"04","publisher":"Elsevier"},{"type":"journal_article","language":[{"iso":"eng"}],"has_accepted_license":"1","issue":"4","page":"880-898","file":[{"date_updated":"2020-07-14T12:47:14Z","file_name":"2018_DiscreteGeometry_Lubiw.pdf","file_id":"5988","date_created":"2019-02-14T11:57:22Z","access_level":"open_access","file_size":556276,"checksum":"e1bff88f1d77001b53b78c485ce048d7","relation":"main_file","creator":"dernst","content_type":"application/pdf"}],"scopus_import":1,"_id":"5986","department":[{"_id":"UlWa"}],"day":"01","date_published":"2019-06-01T00:00:00Z","oa":1,"publication":"Discrete & Computational Geometry","oa_version":"Published Version","article_type":"original","project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"publication_identifier":{"issn":["0179-5376","1432-0444"]},"intvolume":" 61","date_updated":"2020-08-11T10:10:43Z","citation":{"short":"A. Lubiw, Z. Masárová, U. Wagner, Discrete & Computational Geometry 61 (2019) 880–898.","apa":"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. https://doi.org/10.1007/s00454-018-0035-8","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.","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, 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","chicago":"Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” *Discrete & Computational Geometry* 61, no. 4 (2019): 880–98. https://doi.org/10.1007/s00454-018-0035-8."},"title":"A proof of the orbit conjecture for flipping edge-labelled triangulations","month":"06","ddc":["000"],"date_created":"2019-02-14T11:54:08Z","volume":61,"external_id":{"arxiv":["1710.02741"]},"file_date_updated":"2020-07-14T12:47:14Z","publisher":"Springer Nature","author":[{"full_name":"Lubiw, Anna","last_name":"Lubiw","first_name":"Anna"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","last_name":"Masárová","orcid":"0000-0002-6660-1322","full_name":"Masárová, Zuzana"},{"last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli"}],"year":"2019","status":"public","article_processing_charge":"Yes (via OA deal)","quality_controlled":"1","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"doi":"10.1007/s00454-018-0035-8","abstract":[{"lang":"eng","text":"Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm (with 𝑂(𝑛8) being a crude bound on the run-time) to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of 𝑂(𝑛7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture."}],"publication_status":"published","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"7944"},{"status":"public","relation":"earlier_version","id":"683"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"ec_funded":1,"oa":1,"publication":"Discrete Mathematics","date_published":"2019-11-01T00:00:00Z","oa_version":"Preprint","project":[{"name":"Reglas de Conectividad funcional en el hipocampo","_id":"26366136-B435-11E9-9278-68D0E5697425"},{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"}],"publication_identifier":{"issn":["0012-365X"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1901.09955"}],"type":"journal_article","language":[{"iso":"eng"}],"page":"3201-3207","issue":"11","department":[{"_id":"UlWa"}],"_id":"6638","scopus_import":1,"day":"01","author":[{"full_name":"Silva, André ","last_name":"Silva","first_name":"André "},{"full_name":"Arroyo Guevara, Alan M","last_name":"Arroyo Guevara","first_name":"Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Richter","full_name":"Richter, Bruce","first_name":"Bruce"},{"first_name":"Orlando","last_name":"Lee","full_name":"Lee, Orlando"}],"article_processing_charge":"No","quality_controlled":"1","year":"2019","status":"public","doi":"10.1016/j.disc.2019.06.031","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."}],"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","publication_status":"published","month":"11","date_created":"2019-07-14T21:59:20Z","intvolume":" 342","citation":{"chicago":"Silva, André , Alan M Arroyo Guevara, Bruce Richter, and Orlando Lee. “Graphs with at Most One Crossing.” *Discrete Mathematics* 342, no. 11 (2019): 3201–7. 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.","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, pp. 3201–3207, 2019.","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.","apa":"Silva, A., Arroyo Guevara, A. M., Richter, B., & Lee, O. (2019). Graphs with at most one crossing. *Discrete Mathematics*, *342*(11), 3201–3207. https://doi.org/10.1016/j.disc.2019.06.031","short":"A. Silva, A.M. Arroyo Guevara, B. Richter, O. Lee, Discrete Mathematics 342 (2019) 3201–3207."},"title":"Graphs with at most one crossing","date_updated":"2020-08-11T10:10:39Z","external_id":{"arxiv":["1901.09955"]},"volume":342,"publisher":"Elsevier"},{"file":[{"content_type":"application/pdf","creator":"dernst","checksum":"d6d017f8b41291b94d102294fa96ae9c","relation":"main_file","file_size":559837,"access_level":"open_access","date_created":"2019-07-24T06:54:52Z","file_id":"6667","file_name":"2019_LIPICS_Fulek.pdf","date_updated":"2020-07-14T12:47:35Z"}],"page":"38:1-38:13","language":[{"iso":"eng"}],"type":"conference","has_accepted_license":"1","day":"01","scopus_import":1,"department":[{"_id":"UlWa"}],"_id":"6647","oa_version":"Published Version","date_published":"2019-06-01T00:00:00Z","oa":1,"publication":"35th International Symposium on Computational Geometry","publication_identifier":{"isbn":["9783959771047"],"issn":["1868-8969"]},"project":[{"name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281"}],"conference":{"location":"Portland, OR, United States","name":"SoCG 2019: Symposium on Computational Geometry","end_date":"2019-06-21","start_date":"2019-06-18"},"volume":129,"external_id":{"arxiv":["1812.04911"]},"file_date_updated":"2020-07-14T12:47:35Z","intvolume":" 129","citation":{"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.","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.","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.","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","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.","ista":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2019. The crossing Tverberg theorem. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium on Computational Geometry, LIPIcs, vol. 129. 38:1-38:13.","ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. In: *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"},"title":"The crossing Tverberg theorem","date_updated":"2020-08-11T10:10:40Z","month":"06","ddc":["000","510"],"date_created":"2019-07-17T10:35:04Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","alternative_title":["LIPIcs"],"year":"2019","status":"public","quality_controlled":"1","author":[{"first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek"},{"last_name":"Gärtner","full_name":"Gärtner, Bernd","first_name":"Bernd"},{"full_name":"Kupavskii, Andrey","last_name":"Kupavskii","first_name":"Andrey"},{"full_name":"Valtr, Pavel","last_name":"Valtr","first_name":"Pavel"},{"last_name":"Wagner","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"abstract":[{"lang":"eng","text":"The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2."}],"doi":"10.4230/LIPICS.SOCG.2019.38"}]