[{"publication_status":"published","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031492747"],"eissn":["1611-3349"]},"abstract":[{"lang":"eng","text":"A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate the popular faces in an arrangement by inserting a single additional curve. This turns out to be NP-hard; however, it becomes tractable when the number of popular faces is small: We present a probabilistic FPT-approach in the number of popular faces."}],"intvolume":"     14466","date_created":"2024-01-28T23:01:43Z","volume":14466,"oa_version":"Preprint","title":"Removing popular faces in curve arrangements","author":[{"last_name":"De Nooijer","full_name":"De Nooijer, Phoebe","first_name":"Phoebe"},{"first_name":"Soeren","last_name":"Terziadis","full_name":"Terziadis, Soeren"},{"first_name":"Alexandra","full_name":"Weinberger, Alexandra","last_name":"Weinberger"},{"full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","last_name":"Masárová","orcid":"0000-0002-6660-1322","first_name":"Zuzana"},{"last_name":"Mchedlidze","full_name":"Mchedlidze, Tamara","first_name":"Tamara"},{"first_name":"Maarten","full_name":"Löffler, Maarten","last_name":"Löffler"},{"last_name":"Rote","full_name":"Rote, Günter","first_name":"Günter"}],"day":"06","scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"De Nooijer, Phoebe, et al. “Removing Popular Faces in Curve Arrangements.” <i>31st International Symposium on Graph Drawing and Network Visualization</i>, vol. 14466, Springer Nature, 2024, pp. 18–33, doi:<a href=\"https://doi.org/10.1007/978-3-031-49275-4_2\">10.1007/978-3-031-49275-4_2</a>.","apa":"De Nooijer, P., Terziadis, S., Weinberger, A., Masárová, Z., Mchedlidze, T., Löffler, M., &#38; Rote, G. (2024). Removing popular faces in curve arrangements. In <i>31st International Symposium on Graph Drawing and Network Visualization</i> (Vol. 14466, pp. 18–33). Isola delle Femmine, Palermo, Italy: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-49275-4_2\">https://doi.org/10.1007/978-3-031-49275-4_2</a>","chicago":"De Nooijer, Phoebe, Soeren Terziadis, Alexandra Weinberger, Zuzana Masárová, Tamara Mchedlidze, Maarten Löffler, and Günter Rote. “Removing Popular Faces in Curve Arrangements.” In <i>31st International Symposium on Graph Drawing and Network Visualization</i>, 14466:18–33. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-49275-4_2\">https://doi.org/10.1007/978-3-031-49275-4_2</a>.","ista":"De Nooijer P, Terziadis S, Weinberger A, Masárová Z, Mchedlidze T, Löffler M, Rote G. 2024. Removing popular faces in curve arrangements. 31st International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LNCS, vol. 14466, 18–33.","short":"P. De Nooijer, S. Terziadis, A. Weinberger, Z. Masárová, T. Mchedlidze, M. Löffler, G. Rote, in:, 31st International Symposium on Graph Drawing and Network Visualization, Springer Nature, 2024, pp. 18–33.","ieee":"P. De Nooijer <i>et al.</i>, “Removing popular faces in curve arrangements,” in <i>31st International Symposium on Graph Drawing and Network Visualization</i>, Isola delle Femmine, Palermo, Italy, 2024, vol. 14466, pp. 18–33.","ama":"De Nooijer P, Terziadis S, Weinberger A, et al. Removing popular faces in curve arrangements. In: <i>31st International Symposium on Graph Drawing and Network Visualization</i>. Vol 14466. Springer Nature; 2024:18-33. doi:<a href=\"https://doi.org/10.1007/978-3-031-49275-4_2\">10.1007/978-3-031-49275-4_2</a>"},"language":[{"iso":"eng"}],"oa":1,"department":[{"_id":"UlWa"},{"_id":"HeEd"}],"month":"01","arxiv":1,"quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2202.12175"}],"page":"18-33","type":"conference","date_updated":"2025-07-21T07:28:03Z","_id":"14888","publisher":"Springer Nature","doi":"10.1007/978-3-031-49275-4_2","alternative_title":["LNCS"],"article_processing_charge":"No","acknowledgement":"This work was initiated at the 16th European Research Week on Geometric Graphs in Strobl in 2019. A.W. is supported by the Austrian Science Fund (FWF): W1230. S.T. has been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT19035]. A preliminary version of this work has been presented at the 38th European Workshop on Computational Geometry (EuroCG 2022) in Perugia [9]. A full version of this paper, which includes appendices but is otherwise identical, is available as a technical report [10].","conference":{"location":"Isola delle Femmine, Palermo, Italy","end_date":"2023-09-22","start_date":"2023-09-20","name":"GD: Graph Drawing and Network Visualization"},"date_published":"2024-01-06T00:00:00Z","project":[{"grant_number":"101087907","name":"A quantum hybrid of atoms and milligram-scale pendulums: towards gravitational quantum mechanics","_id":"bdb2a702-d553-11ed-ba76-f12e3e5a3bc6"}],"status":"public","publication":"31st International Symposium on Graph Drawing and Network Visualization","external_id":{"arxiv":["2202.12175"]},"year":"2024"},{"acknowledgement":"This work was begun at the University of Waterloo and was partially supported by the Natural Sciences and Engineering Council of Canada (NSERC).\r\n","date_published":"2023-01-18T00:00:00Z","publication":"Discrete Mathematics and Theoretical Computer Science","status":"public","year":"2023","external_id":{"arxiv":["1903.06981"]},"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"7950"}]},"quality_controlled":"1","ddc":["000"],"date_updated":"2024-01-04T12:42:09Z","_id":"12833","type":"journal_article","doi":"10.46298/DMTCS.8383","article_processing_charge":"No","publisher":"EPI Sciences","issue":"2","citation":{"mla":"Biniaz, Ahmad, et al. “Token Swapping on Trees.” <i>Discrete Mathematics and Theoretical Computer Science</i>, vol. 24, no. 2, 9, EPI Sciences, 2023, doi:<a href=\"https://doi.org/10.46298/DMTCS.8383\">10.46298/DMTCS.8383</a>.","apa":"Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte, A. (2023). Token swapping on trees. <i>Discrete Mathematics and Theoretical Computer Science</i>. EPI Sciences. <a href=\"https://doi.org/10.46298/DMTCS.8383\">https://doi.org/10.46298/DMTCS.8383</a>","chicago":"Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token Swapping on Trees.” <i>Discrete Mathematics and Theoretical Computer Science</i>. EPI Sciences, 2023. <a href=\"https://doi.org/10.46298/DMTCS.8383\">https://doi.org/10.46298/DMTCS.8383</a>.","ista":"Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec J, Turcotte A. 2023. Token swapping on trees. Discrete Mathematics and Theoretical Computer Science. 24(2), 9.","short":"A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec, A. Turcotte, Discrete Mathematics and Theoretical Computer Science 24 (2023).","ieee":"A. Biniaz <i>et al.</i>, “Token swapping on trees,” <i>Discrete Mathematics and Theoretical Computer Science</i>, vol. 24, no. 2. EPI Sciences, 2023.","ama":"Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. <i>Discrete Mathematics and Theoretical Computer Science</i>. 2023;24(2). doi:<a href=\"https://doi.org/10.46298/DMTCS.8383\">10.46298/DMTCS.8383</a>"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa":1,"language":[{"iso":"eng"}],"department":[{"_id":"KrCh"},{"_id":"HeEd"},{"_id":"UlWa"}],"file":[{"relation":"main_file","checksum":"439102ea4f6e2aeefd7107dfb9ccf532","file_name":"2022_DMTCS_Biniaz.pdf","success":1,"content_type":"application/pdf","access_level":"open_access","file_id":"12844","file_size":2072197,"date_created":"2023-04-17T08:10:28Z","date_updated":"2023-04-17T08:10:28Z","creator":"dernst"}],"article_number":"9","month":"01","arxiv":1,"publication_status":"published","publication_identifier":{"issn":["1462-7264"],"eissn":["1365-8050"]},"file_date_updated":"2023-04-17T08:10:28Z","has_accepted_license":"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","image":"/images/cc_by.png","short":"CC BY (4.0)"},"intvolume":"        24","abstract":[{"text":"The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete. We present some partial results: 1. 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. 2. 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. 3. A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars. In this version, tokens and vertices have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.","lang":"eng"}],"volume":24,"article_type":"original","date_created":"2023-04-16T22:01:08Z","author":[{"full_name":"Biniaz, Ahmad","last_name":"Biniaz","first_name":"Ahmad"},{"last_name":"Jain","full_name":"Jain, Kshitij","first_name":"Kshitij"},{"first_name":"Anna","last_name":"Lubiw","full_name":"Lubiw, Anna"},{"last_name":"Masárová","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","full_name":"Masárová, Zuzana","first_name":"Zuzana","orcid":"0000-0002-6660-1322"},{"full_name":"Miltzow, Tillmann","last_name":"Miltzow","first_name":"Tillmann"},{"last_name":"Mondal","full_name":"Mondal, Debajyoti","first_name":"Debajyoti"},{"first_name":"Anurag Murty","last_name":"Naredla","full_name":"Naredla, Anurag Murty"},{"full_name":"Tkadlec, Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","orcid":"0000-0002-1097-9684","first_name":"Josef"},{"full_name":"Turcotte, Alexi","last_name":"Turcotte","first_name":"Alexi"}],"day":"18","scopus_import":"1","oa_version":"Published Version","title":"Token swapping on trees"},{"external_id":{"arxiv":["2101.03928"]},"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"9296"}]},"year":"2022","project":[{"call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","grant_number":"Z00342","name":"The Wittgenstein Prize","call_identifier":"FWF"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407","call_identifier":"FWF"}],"status":"public","publication":"Journal of Graph Algorithms and Applications","date_published":"2022-06-01T00:00:00Z","acknowledgement":"A.A. funded by the Marie Sklodowska-Curie grant agreement No 754411. Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23 (RiSE).","ec_funded":1,"publisher":"Brown University","doi":"10.7155/jgaa.00591","article_processing_charge":"No","type":"journal_article","date_updated":"2023-02-23T13:54:21Z","_id":"11938","ddc":["000"],"page":"225-240","quality_controlled":"1","month":"06","arxiv":1,"file":[{"file_name":"2022_JourGraphAlgorithmsApplic_Aichholzer.pdf","success":1,"content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"dc6e255e3558faff924fd9e370886c11","date_created":"2022-08-22T06:42:42Z","file_size":694538,"creator":"dernst","date_updated":"2022-08-22T06:42:42Z","file_id":"11940"}],"department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"language":[{"iso":"eng"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"2","citation":{"ista":"Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec J, Vogtenhuber B. 2022. On compatible matchings. Journal of Graph Algorithms and Applications. 26(2), 225–240.","chicago":"Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible Matchings.” <i>Journal of Graph Algorithms and Applications</i>. Brown University, 2022. <a href=\"https://doi.org/10.7155/jgaa.00591\">https://doi.org/10.7155/jgaa.00591</a>.","apa":"Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2022). On compatible matchings. <i>Journal of Graph Algorithms and Applications</i>. Brown University. <a href=\"https://doi.org/10.7155/jgaa.00591\">https://doi.org/10.7155/jgaa.00591</a>","mla":"Aichholzer, Oswin, et al. “On Compatible Matchings.” <i>Journal of Graph Algorithms and Applications</i>, vol. 26, no. 2, Brown University, 2022, pp. 225–40, doi:<a href=\"https://doi.org/10.7155/jgaa.00591\">10.7155/jgaa.00591</a>.","ama":"Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. <i>Journal of Graph Algorithms and Applications</i>. 2022;26(2):225-240. doi:<a href=\"https://doi.org/10.7155/jgaa.00591\">10.7155/jgaa.00591</a>","ieee":"O. Aichholzer <i>et al.</i>, “On compatible matchings,” <i>Journal of Graph Algorithms and Applications</i>, vol. 26, no. 2. Brown University, pp. 225–240, 2022.","short":"O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, Journal of Graph Algorithms and Applications 26 (2022) 225–240."},"oa_version":"Published Version","title":"On compatible matchings","author":[{"first_name":"Oswin","full_name":"Aichholzer, Oswin","last_name":"Aichholzer"},{"id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","full_name":"Arroyo Guevara, Alan M","last_name":"Arroyo Guevara","first_name":"Alan M","orcid":"0000-0003-2401-8670"},{"last_name":"Masárová","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","first_name":"Zuzana"},{"last_name":"Parada","full_name":"Parada, Irene","first_name":"Irene"},{"first_name":"Daniel","full_name":"Perz, Daniel","last_name":"Perz"},{"last_name":"Pilz","full_name":"Pilz, Alexander","first_name":"Alexander"},{"first_name":"Josef","orcid":"0000-0002-1097-9684","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","full_name":"Tkadlec, Josef","last_name":"Tkadlec"},{"first_name":"Birgit","full_name":"Vogtenhuber, Birgit","last_name":"Vogtenhuber"}],"scopus_import":"1","day":"01","article_type":"original","date_created":"2022-08-21T22:01:56Z","volume":26,"intvolume":"        26","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","image":"/images/cc_by.png","short":"CC BY (4.0)"},"abstract":[{"text":"A matching is compatible to two or more labeled point sets of size n with labels {1, . . . , n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled sets of n points in convex position there exists a compatible matching with ⌊√2n + 1 − 1⌋ edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n1/ℓ). As a corresponding upper bound, we use probabilistic arguments to show that for any ℓ given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges. Finally, we show that Θ(log n) copies of any set of n points are necessary and sufficient for the existence of labelings of these point sets such that any compatible matching consists only of a single edge.","lang":"eng"}],"has_accepted_license":"1","publication_identifier":{"issn":["1526-1719"]},"publication_status":"published","file_date_updated":"2022-08-22T06:42:42Z"},{"arxiv":1,"month":"02","department":[{"_id":"HeEd"}],"article_number":"101700","oa":1,"language":[{"iso":"eng"}],"citation":{"ieee":"O. Aichholzer <i>et al.</i>, “Folding polyominoes with holes into a cube,” <i>Computational Geometry: Theory and Applications</i>, vol. 93. Elsevier, 2021.","short":"O. Aichholzer, H.A. Akitaya, K.C. Cheung, E.D. Demaine, M.L. Demaine, S.P. Fekete, L. Kleist, I. Kostitsyna, M. Löffler, Z. Masárová, K. Mundilova, C. Schmidt, Computational Geometry: Theory and Applications 93 (2021).","ama":"Aichholzer O, Akitaya HA, Cheung KC, et al. Folding polyominoes with holes into a cube. <i>Computational Geometry: Theory and Applications</i>. 2021;93. doi:<a href=\"https://doi.org/10.1016/j.comgeo.2020.101700\">10.1016/j.comgeo.2020.101700</a>","apa":"Aichholzer, O., Akitaya, H. A., Cheung, K. C., Demaine, E. D., Demaine, M. L., Fekete, S. P., … Schmidt, C. (2021). Folding polyominoes with holes into a cube. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.comgeo.2020.101700\">https://doi.org/10.1016/j.comgeo.2020.101700</a>","mla":"Aichholzer, Oswin, et al. “Folding Polyominoes with Holes into a Cube.” <i>Computational Geometry: Theory and Applications</i>, vol. 93, 101700, Elsevier, 2021, doi:<a href=\"https://doi.org/10.1016/j.comgeo.2020.101700\">10.1016/j.comgeo.2020.101700</a>.","ista":"Aichholzer O, Akitaya HA, Cheung KC, Demaine ED, Demaine ML, Fekete SP, Kleist L, Kostitsyna I, Löffler M, Masárová Z, Mundilova K, Schmidt C. 2021. Folding polyominoes with holes into a cube. Computational Geometry: Theory and Applications. 93, 101700.","chicago":"Aichholzer, Oswin, Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Linda Kleist, et al. “Folding Polyominoes with Holes into a Cube.” <i>Computational Geometry: Theory and Applications</i>. Elsevier, 2021. <a href=\"https://doi.org/10.1016/j.comgeo.2020.101700\">https://doi.org/10.1016/j.comgeo.2020.101700</a>."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","author":[{"last_name":"Aichholzer","full_name":"Aichholzer, Oswin","first_name":"Oswin"},{"last_name":"Akitaya","full_name":"Akitaya, Hugo A.","first_name":"Hugo A."},{"full_name":"Cheung, Kenneth C.","last_name":"Cheung","first_name":"Kenneth C."},{"last_name":"Demaine","full_name":"Demaine, Erik D.","first_name":"Erik D."},{"first_name":"Martin L.","last_name":"Demaine","full_name":"Demaine, Martin L."},{"full_name":"Fekete, Sándor P.","last_name":"Fekete","first_name":"Sándor P."},{"first_name":"Linda","last_name":"Kleist","full_name":"Kleist, Linda"},{"last_name":"Kostitsyna","full_name":"Kostitsyna, Irina","first_name":"Irina"},{"first_name":"Maarten","full_name":"Löffler, Maarten","last_name":"Löffler"},{"first_name":"Zuzana","orcid":"0000-0002-6660-1322","full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","last_name":"Masárová"},{"first_name":"Klara","last_name":"Mundilova","full_name":"Mundilova, Klara"},{"last_name":"Schmidt","full_name":"Schmidt, Christiane","first_name":"Christiane"}],"scopus_import":"1","day":"01","oa_version":"Preprint","title":"Folding polyominoes with holes into a cube","volume":93,"article_type":"original","date_created":"2020-08-30T22:01:09Z","intvolume":"        93","abstract":[{"lang":"eng","text":"When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with one or several holes to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special “basic” holes guarantee foldability."}],"publication_status":"published","publication_identifier":{"issn":["09257721"]},"isi":1,"year":"2021","external_id":{"arxiv":["1910.09917"],"isi":["000579185100004"]},"related_material":{"record":[{"id":"6989","relation":"shorter_version","status":"public"}]},"project":[{"call_identifier":"FWF","grant_number":"Z00342","name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425"}],"publication":"Computational Geometry: Theory and Applications","status":"public","acknowledgement":"This research was performed in part at the 33rd Bellairs Winter Workshop on Computational Geometry. We thank all other participants for a fruitful atmosphere. H. Akitaya was supported by NSF CCF-1422311 & 1423615. Z. Masárová was partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.","date_published":"2021-02-01T00:00:00Z","doi":"10.1016/j.comgeo.2020.101700","article_processing_charge":"No","publisher":"Elsevier","date_updated":"2023-08-04T10:57:42Z","_id":"8317","type":"journal_article","main_file_link":[{"url":"https://arxiv.org/abs/1910.09917v3","open_access":"1"}],"quality_controlled":"1"},{"publisher":"Springer Nature","doi":"10.1007/978-3-030-68211-8_18","article_processing_charge":"No","alternative_title":["LNCS"],"type":"conference","date_updated":"2023-02-21T16:33:44Z","_id":"9296","page":"221-233","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2101.03928"}],"external_id":{"arxiv":["2101.03928"]},"related_material":{"record":[{"id":"11938","relation":"later_version","status":"public"}]},"year":"2021","project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","grant_number":"Z00342","name":"The Wittgenstein Prize","call_identifier":"FWF"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425"}],"publication":"15th International Conference on Algorithms and Computation","status":"public","acknowledgement":"A.A. funded by the Marie Skłodowska-Curie grant agreement No. 754411. Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23 (RiSE).","conference":{"end_date":"2021-03-02","start_date":"2021-02-28","name":"WALCOM: Algorithms and Computation","location":"Yangon, Myanmar"},"date_published":"2021-02-16T00:00:00Z","ec_funded":1,"oa_version":"Preprint","title":"On compatible matchings","author":[{"first_name":"Oswin","last_name":"Aichholzer","full_name":"Aichholzer, Oswin"},{"orcid":"0000-0003-2401-8670","first_name":"Alan M","full_name":"Arroyo Guevara, Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","last_name":"Arroyo Guevara"},{"last_name":"Masárová","full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","orcid":"0000-0002-6660-1322"},{"full_name":"Parada, Irene","last_name":"Parada","first_name":"Irene"},{"full_name":"Perz, Daniel","last_name":"Perz","first_name":"Daniel"},{"first_name":"Alexander","full_name":"Pilz, Alexander","last_name":"Pilz"},{"first_name":"Josef","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec"},{"first_name":"Birgit","full_name":"Vogtenhuber, Birgit","last_name":"Vogtenhuber"}],"day":"16","scopus_import":"1","date_created":"2021-03-28T22:01:41Z","volume":12635,"intvolume":"     12635","abstract":[{"lang":"eng","text":" matching is compatible to two or more labeled point sets of size n with labels   {1,…,n}  if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of n points there exists a compatible matching with   ⌊2n−−√⌋  edges. More generally, for any   ℓ  labeled point sets we construct compatible matchings of size   Ω(n1/ℓ) . As a corresponding upper bound, we use probabilistic arguments to show that for any   ℓ  given sets of n points there exists a labeling of each set such that the largest compatible matching has   O(n2/(ℓ+1))  edges. Finally, we show that   Θ(logn)  copies of any set of n points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge."}],"publication_status":"published","publication_identifier":{"issn":["03029743"],"isbn":["9783030682101"],"eissn":["16113349"]},"arxiv":1,"month":"02","department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"language":[{"iso":"eng"}],"oa":1,"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","citation":{"apa":"Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2021). On compatible matchings. In <i>15th International Conference on Algorithms and Computation</i> (Vol. 12635, pp. 221–233). Yangon, Myanmar: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-68211-8_18\">https://doi.org/10.1007/978-3-030-68211-8_18</a>","mla":"Aichholzer, Oswin, et al. “On Compatible Matchings.” <i>15th International Conference on Algorithms and Computation</i>, vol. 12635, Springer Nature, 2021, pp. 221–33, doi:<a href=\"https://doi.org/10.1007/978-3-030-68211-8_18\">10.1007/978-3-030-68211-8_18</a>.","chicago":"Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible Matchings.” In <i>15th International Conference on Algorithms and Computation</i>, 12635:221–33. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-68211-8_18\">https://doi.org/10.1007/978-3-030-68211-8_18</a>.","ista":"Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec J, Vogtenhuber B. 2021. On compatible matchings. 15th International Conference on Algorithms and Computation. WALCOM: Algorithms and Computation, LNCS, vol. 12635, 221–233.","ieee":"O. Aichholzer <i>et al.</i>, “On compatible matchings,” in <i>15th International Conference on Algorithms and Computation</i>, Yangon, Myanmar, 2021, vol. 12635, pp. 221–233.","short":"O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, in:, 15th International Conference on Algorithms and Computation, Springer Nature, 2021, pp. 221–233.","ama":"Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. In: <i>15th International Conference on Algorithms and Computation</i>. Vol 12635. Springer Nature; 2021:221-233. doi:<a href=\"https://doi.org/10.1007/978-3-030-68211-8_18\">10.1007/978-3-030-68211-8_18</a>"}},{"publication_identifier":{"isbn":["978-3-99078-005-3"],"issn":["2663-337X"]},"publication_status":"published","file_date_updated":"2020-07-14T12:48:05Z","license":"https://creativecommons.org/licenses/by-sa/4.0/","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"}],"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"},"has_accepted_license":"1","date_created":"2020-06-08T00:49:46Z","title":"Reconfiguration problems","oa_version":"Published Version","author":[{"orcid":"0000-0002-6660-1322","first_name":"Zuzana","full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","last_name":"Masárová"}],"day":"09","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"short":"Z. Masárová, Reconfiguration Problems, Institute of Science and Technology Austria, 2020.","ieee":"Z. Masárová, “Reconfiguration problems,” Institute of Science and Technology Austria, 2020.","ama":"Masárová Z. Reconfiguration problems. 2020. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7944\">10.15479/AT:ISTA:7944</a>","mla":"Masárová, Zuzana. <i>Reconfiguration Problems</i>. Institute of Science and Technology Austria, 2020, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7944\">10.15479/AT:ISTA:7944</a>.","apa":"Masárová, Z. (2020). <i>Reconfiguration problems</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:7944\">https://doi.org/10.15479/AT:ISTA:7944</a>","ista":"Masárová Z. 2020. Reconfiguration problems. Institute of Science and Technology Austria.","chicago":"Masárová, Zuzana. “Reconfiguration Problems.” Institute of Science and Technology Austria, 2020. <a href=\"https://doi.org/10.15479/AT:ISTA:7944\">https://doi.org/10.15479/AT:ISTA:7944</a>."},"language":[{"iso":"eng"}],"oa":1,"file":[{"relation":"main_file","checksum":"df688bc5a82b50baee0b99d25fc7b7f0","file_name":"THESIS_Zuzka_Masarova.pdf","content_type":"application/pdf","access_level":"open_access","file_id":"7945","date_created":"2020-06-08T00:34:00Z","file_size":13661779,"creator":"zmasarov","date_updated":"2020-07-14T12:48:05Z"},{"creator":"zmasarov","date_updated":"2020-07-14T12:48:05Z","date_created":"2020-06-08T00:35:30Z","file_size":32184006,"file_id":"7946","content_type":"application/zip","access_level":"closed","file_name":"THESIS_Zuzka_Masarova_SOURCE_FILES.zip","checksum":"45341a35b8f5529c74010b7af43ac188","relation":"source_file"}],"department":[{"_id":"HeEd"},{"_id":"UlWa"}],"month":"06","supervisor":[{"last_name":"Wagner","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","orcid":"0000-0002-1494-0568"},{"orcid":"0000-0002-9823-6833","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner"}],"ddc":["516","514"],"page":"160","type":"dissertation","date_updated":"2023-09-07T13:17:37Z","_id":"7944","publisher":"Institute of Science and Technology Austria","doi":"10.15479/AT:ISTA:7944","article_processing_charge":"No","alternative_title":["ISTA Thesis"],"date_published":"2020-06-09T00:00:00Z","status":"public","degree_awarded":"PhD","keyword":["reconfiguration","reconfiguration graph","triangulations","flip","constrained triangulations","shellability","piecewise-linear balls","token swapping","trees","coloured weighted token swapping"],"related_material":{"record":[{"id":"7950","relation":"part_of_dissertation","status":"public"},{"relation":"part_of_dissertation","status":"public","id":"5986"}]},"year":"2020"},{"date_published":"2019-03-16T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ama":"Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. <i>arXiv</i>.","short":"A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec, A. Turcotte, ArXiv (n.d.).","ieee":"A. Biniaz <i>et al.</i>, “Token swapping on trees,” <i>arXiv</i>. .","chicago":"Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token Swapping on Trees.” <i>ArXiv</i>, n.d.","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.","mla":"Biniaz, Ahmad, et al. “Token Swapping on Trees.” <i>ArXiv</i>, 1903.06981.","apa":"Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte, A. (n.d.). Token swapping on trees. <i>arXiv</i>."},"language":[{"iso":"eng"}],"status":"public","publication":"arXiv","oa":1,"article_number":"1903.06981","department":[{"_id":"HeEd"},{"_id":"UlWa"},{"_id":"KrCh"}],"external_id":{"arxiv":["1903.06981"]},"arxiv":1,"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"7944"},{"id":"12833","status":"public","relation":"later_version"}]},"month":"03","year":"2019","publication_status":"submitted","main_file_link":[{"url":"https://arxiv.org/abs/1903.06981","open_access":"1"}],"abstract":[{"text":"The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex.  The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete.  We present some partial results:\r\n1.  An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan.\r\n2.  Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3.  Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2.\r\n3.  A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars.  In this version, tokens and  vertices  have  colours,  and  colours  have  weights.   The  goal  is  to  get  every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.","lang":"eng"}],"type":"preprint","date_created":"2020-06-08T12:25:25Z","date_updated":"2024-01-04T12:42:08Z","_id":"7950","title":"Token swapping on trees","oa_version":"Preprint","author":[{"last_name":"Biniaz","full_name":"Biniaz, Ahmad","first_name":"Ahmad"},{"full_name":"Jain, Kshitij","last_name":"Jain","first_name":"Kshitij"},{"first_name":"Anna","last_name":"Lubiw","full_name":"Lubiw, Anna"},{"last_name":"Masárová","full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","orcid":"0000-0002-6660-1322"},{"full_name":"Miltzow, Tillmann","last_name":"Miltzow","first_name":"Tillmann"},{"full_name":"Mondal, Debajyoti","last_name":"Mondal","first_name":"Debajyoti"},{"full_name":"Naredla, Anurag Murty","last_name":"Naredla","first_name":"Anurag Murty"},{"orcid":"0000-0002-1097-9684","first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","full_name":"Tkadlec, Josef","last_name":"Tkadlec"},{"first_name":"Alexi","last_name":"Turcotte","full_name":"Turcotte, Alexi"}],"day":"16","article_processing_charge":"No"},{"arxiv":1,"month":"08","department":[{"_id":"HeEd"}],"language":[{"iso":"eng"}],"oa":1,"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","citation":{"ama":"Aichholzer O, Akitaya HA, Cheung KC, et al. Folding polyominoes with holes into a cube. In: <i>Proceedings of the 31st Canadian Conference on Computational Geometry</i>. Canadian Conference on Computational Geometry; 2019:164-170.","ieee":"O. Aichholzer <i>et al.</i>, “Folding polyominoes with holes into a cube,” in <i>Proceedings of the 31st Canadian Conference on Computational Geometry</i>, Edmonton, Canada, 2019, pp. 164–170.","short":"O. Aichholzer, H.A. Akitaya, K.C. Cheung, E.D. Demaine, M.L. Demaine, S.P. Fekete, L. Kleist, I. Kostitsyna, M. Löffler, Z. Masárová, K. Mundilova, C. Schmidt, in:, Proceedings of the 31st Canadian Conference on Computational Geometry, Canadian Conference on Computational Geometry, 2019, pp. 164–170.","ista":"Aichholzer O, Akitaya HA, Cheung KC, Demaine ED, Demaine ML, Fekete SP, Kleist L, Kostitsyna I, Löffler M, Masárová Z, Mundilova K, Schmidt C. 2019. Folding polyominoes with holes into a cube. Proceedings of the 31st Canadian Conference on Computational Geometry. CCCG: Canadian Conference in Computational Geometry, 164–170.","chicago":"Aichholzer, Oswin, Hugo A Akitaya, Kenneth C Cheung, Erik D Demaine, Martin L Demaine, Sandor P Fekete, Linda Kleist, et al. “Folding Polyominoes with Holes into a Cube.” In <i>Proceedings of the 31st Canadian Conference on Computational Geometry</i>, 164–70. Canadian Conference on Computational Geometry, 2019.","apa":"Aichholzer, O., Akitaya, H. A., Cheung, K. C., Demaine, E. D., Demaine, M. L., Fekete, S. P., … Schmidt, C. (2019). Folding polyominoes with holes into a cube. In <i>Proceedings of the 31st Canadian Conference on Computational Geometry</i> (pp. 164–170). Edmonton, Canada: Canadian Conference on Computational Geometry.","mla":"Aichholzer, Oswin, et al. “Folding Polyominoes with Holes into a Cube.” <i>Proceedings of the 31st Canadian Conference on Computational Geometry</i>, Canadian Conference on Computational Geometry, 2019, pp. 164–70."},"title":"Folding polyominoes with holes into a cube","oa_version":"Published Version","scopus_import":"1","day":"01","author":[{"first_name":"Oswin","full_name":"Aichholzer, Oswin","last_name":"Aichholzer"},{"first_name":"Hugo A","full_name":"Akitaya, Hugo A","last_name":"Akitaya"},{"full_name":"Cheung, Kenneth C","last_name":"Cheung","first_name":"Kenneth C"},{"last_name":"Demaine","full_name":"Demaine, Erik D","first_name":"Erik D"},{"first_name":"Martin L","full_name":"Demaine, Martin L","last_name":"Demaine"},{"first_name":"Sandor P","full_name":"Fekete, Sandor P","last_name":"Fekete"},{"first_name":"Linda","last_name":"Kleist","full_name":"Kleist, Linda"},{"first_name":"Irina","full_name":"Kostitsyna, Irina","last_name":"Kostitsyna"},{"first_name":"Maarten","last_name":"Löffler","full_name":"Löffler, Maarten"},{"first_name":"Zuzana","orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","full_name":"Masárová, Zuzana","last_name":"Masárová"},{"last_name":"Mundilova","full_name":"Mundilova, Klara","first_name":"Klara"},{"first_name":"Christiane","full_name":"Schmidt, Christiane","last_name":"Schmidt"}],"date_created":"2019-11-04T16:46:11Z","abstract":[{"text":"When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with hole(s) to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special simple holes guarantee foldability. ","lang":"eng"}],"publication_status":"published","related_material":{"record":[{"relation":"extended_version","status":"public","id":"8317"}]},"external_id":{"arxiv":["1910.09917"]},"year":"2019","status":"public","publication":"Proceedings of the 31st Canadian Conference on Computational Geometry","date_published":"2019-08-01T00:00:00Z","conference":{"start_date":"2019-08-08","end_date":"2019-08-10","name":"CCCG: Canadian Conference in Computational Geometry","location":"Edmonton, Canada"},"acknowledgement":"This research was performed in part at the 33rd BellairsWinter  Workshop  on  Computational  Geometry.    Wethank all other participants for a fruitful atmosphere.","publisher":"Canadian Conference on Computational Geometry","article_processing_charge":"No","type":"conference","_id":"6989","date_updated":"2023-08-04T10:57:42Z","page":"164-170","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://cccg.ca/proceedings/2019/proceedings.pdf"}]},{"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"publication_status":"published","file_date_updated":"2020-07-14T12:47:14Z","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"}],"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","image":"/images/cc_by.png","short":"CC BY (4.0)"},"intvolume":"        61","has_accepted_license":"1","article_type":"original","date_created":"2019-02-14T11:54:08Z","volume":61,"title":"A proof of the orbit conjecture for flipping edge-labelled triangulations","oa_version":"Published Version","author":[{"full_name":"Lubiw, Anna","last_name":"Lubiw","first_name":"Anna"},{"orcid":"0000-0002-6660-1322","first_name":"Zuzana","full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","last_name":"Masárová"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568"}],"scopus_import":"1","day":"01","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","issue":"4","citation":{"ama":"Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping edge-labelled triangulations. <i>Discrete &#38; Computational Geometry</i>. 2019;61(4):880-898. doi:<a href=\"https://doi.org/10.1007/s00454-018-0035-8\">10.1007/s00454-018-0035-8</a>","ieee":"A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for flipping edge-labelled triangulations,” <i>Discrete &#38; Computational Geometry</i>, vol. 61, no. 4. Springer Nature, pp. 880–898, 2019.","short":"A. Lubiw, Z. Masárová, U. Wagner, Discrete &#38; Computational Geometry 61 (2019) 880–898.","ista":"Lubiw A, Masárová Z, Wagner U. 2019. A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete &#38; Computational Geometry. 61(4), 880–898.","chicago":"Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/s00454-018-0035-8\">https://doi.org/10.1007/s00454-018-0035-8</a>.","apa":"Lubiw, A., Masárová, Z., &#38; Wagner, U. (2019). A proof of the orbit conjecture for flipping edge-labelled triangulations. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-018-0035-8\">https://doi.org/10.1007/s00454-018-0035-8</a>","mla":"Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” <i>Discrete &#38; Computational Geometry</i>, vol. 61, no. 4, Springer Nature, 2019, pp. 880–98, doi:<a href=\"https://doi.org/10.1007/s00454-018-0035-8\">10.1007/s00454-018-0035-8</a>."},"language":[{"iso":"eng"}],"oa":1,"file":[{"file_id":"5988","file_size":556276,"date_created":"2019-02-14T11:57:22Z","date_updated":"2020-07-14T12:47:14Z","creator":"dernst","relation":"main_file","checksum":"e1bff88f1d77001b53b78c485ce048d7","file_name":"2018_DiscreteGeometry_Lubiw.pdf","content_type":"application/pdf","access_level":"open_access"}],"department":[{"_id":"UlWa"}],"month":"06","arxiv":1,"quality_controlled":"1","ddc":["000"],"page":"880-898","type":"journal_article","date_updated":"2023-09-07T13:17:36Z","_id":"5986","publisher":"Springer Nature","doi":"10.1007/s00454-018-0035-8","article_processing_charge":"Yes (via OA deal)","date_published":"2019-06-01T00:00:00Z","project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"status":"public","publication":"Discrete & Computational Geometry","external_id":{"isi":["000466130000009"],"arxiv":["1710.02741"]},"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"683"},{"status":"public","relation":"dissertation_contains","id":"7944"}]},"isi":1,"year":"2019"},{"file":[{"access_level":"open_access","content_type":"application/pdf","file_name":"IST-2017-896-v1+1_LIPIcs-SoCG-2017-49.pdf","checksum":"24fdde981cc513352a78dcf9b0660ae9","relation":"main_file","creator":"system","date_updated":"2020-07-14T12:47:41Z","date_created":"2018-12-12T10:17:12Z","file_size":710007,"file_id":"5265"}],"article_number":"49","department":[{"_id":"UlWa"}],"month":"06","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.49\">10.4230/LIPIcs.SoCG.2017.49</a>","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.","short":"A. Lubiw, Z. Masárová, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","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. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.49\">https://doi.org/10.4230/LIPIcs.SoCG.2017.49</a>.","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.","apa":"Lubiw, A., Masárová, Z., &#38; 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. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.49\">https://doi.org/10.4230/LIPIcs.SoCG.2017.49</a>","mla":"Lubiw, Anna, et al. <i>A Proof of the Orbit Conjecture for Flipping Edge Labelled Triangulations</i>. Vol. 77, 49, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.49\">10.4230/LIPIcs.SoCG.2017.49</a>."},"language":[{"iso":"eng"}],"pubrep_id":"896","oa":1,"date_created":"2018-12-11T11:47:54Z","volume":77,"title":"A proof of the orbit conjecture for flipping edge labelled triangulations","oa_version":"Published Version","scopus_import":1,"day":"01","author":[{"full_name":"Lubiw, Anna","last_name":"Lubiw","first_name":"Anna"},{"orcid":"0000-0002-6660-1322","first_name":"Zuzana","full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","last_name":"Masárová"},{"orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"file_date_updated":"2020-07-14T12:47:41Z","publication_status":"published","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 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.","lang":"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","image":"/images/cc_by.png","short":"CC BY (4.0)"},"intvolume":"        77","has_accepted_license":"1","publist_id":"7033","related_material":{"record":[{"id":"5986","status":"public","relation":"later_version"}]},"year":"2017","date_published":"2017-06-01T00:00:00Z","conference":{"end_date":"2017-07-07","start_date":"2017-07-04","name":"SoCG: Symposium on Computational Geometry","location":"Brisbane, Australia"},"status":"public","type":"conference","_id":"683","date_updated":"2023-09-05T15:01:43Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","alternative_title":["LIPIcs"],"doi":"10.4230/LIPIcs.SoCG.2017.49","quality_controlled":"1","ddc":["514","516"]}]