[{"year":"2024","day":"06","publication":"31st International Symposium on Graph Drawing and Network Visualization","page":"18-33","doi":"10.1007/978-3-031-49275-4_2","date_published":"2024-01-06T00:00:00Z","date_created":"2024-01-28T23:01:43Z","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].","quality_controlled":"1","publisher":"Springer Nature","oa":1,"citation":{"mla":"De Nooijer, Phoebe, et al. “Removing Popular Faces in Curve Arrangements.” 31st International Symposium on Graph Drawing and Network Visualization, vol. 14466, Springer Nature, 2024, pp. 18–33, doi:10.1007/978-3-031-49275-4_2.","apa":"De Nooijer, P., Terziadis, S., Weinberger, A., Masárová, Z., Mchedlidze, T., Löffler, M., & Rote, G. (2024). Removing popular faces in curve arrangements. In 31st International Symposium on Graph Drawing and Network Visualization (Vol. 14466, pp. 18–33). Isola delle Femmine, Palermo, Italy: Springer Nature. https://doi.org/10.1007/978-3-031-49275-4_2","ama":"De Nooijer P, Terziadis S, Weinberger A, et al. Removing popular faces in curve arrangements. In: 31st International Symposium on Graph Drawing and Network Visualization. Vol 14466. Springer Nature; 2024:18-33. doi:10.1007/978-3-031-49275-4_2","ieee":"P. De Nooijer et al., “Removing popular faces in curve arrangements,” in 31st International Symposium on Graph Drawing and Network Visualization, Isola delle Femmine, Palermo, Italy, 2024, vol. 14466, pp. 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.","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 31st International Symposium on Graph Drawing and Network Visualization, 14466:18–33. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-49275-4_2.","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."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Phoebe","full_name":"De Nooijer, Phoebe","last_name":"De Nooijer"},{"last_name":"Terziadis","full_name":"Terziadis, Soeren","first_name":"Soeren"},{"first_name":"Alexandra","last_name":"Weinberger","full_name":"Weinberger, Alexandra"},{"full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","last_name":"Masárová","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana"},{"last_name":"Mchedlidze","full_name":"Mchedlidze, Tamara","first_name":"Tamara"},{"full_name":"Löffler, Maarten","last_name":"Löffler","first_name":"Maarten"},{"last_name":"Rote","full_name":"Rote, Günter","first_name":"Günter"}],"external_id":{"arxiv":["2202.12175"]},"article_processing_charge":"No","title":"Removing popular faces in curve arrangements","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031492747"],"eissn":["1611-3349"]},"publication_status":"published","language":[{"iso":"eng"}],"volume":14466,"abstract":[{"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.","lang":"eng"}],"oa_version":"Preprint","alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2202.12175"}],"month":"01","intvolume":" 14466","date_updated":"2024-01-29T09:45:06Z","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"_id":"14888","type":"conference","conference":{"name":"GD: Graph Drawing and Network Visualization","end_date":"2023-09-22","location":"Isola delle Femmine, Palermo, Italy","start_date":"2023-09-20"},"status":"public"},{"article_type":"original","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","_id":"12833","file_date_updated":"2023-04-17T08:10:28Z","department":[{"_id":"KrCh"},{"_id":"HeEd"},{"_id":"UlWa"}],"date_updated":"2024-01-04T12:42:09Z","ddc":["000"],"scopus_import":"1","month":"01","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"}],"oa_version":"Published Version","volume":24,"related_material":{"record":[{"status":"public","id":"7950","relation":"earlier_version"}]},"issue":"2","license":"https://creativecommons.org/licenses/by/4.0/","publication_identifier":{"issn":["1462-7264"],"eissn":["1365-8050"]},"publication_status":"published","file":[{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"12844","checksum":"439102ea4f6e2aeefd7107dfb9ccf532","success":1,"date_updated":"2023-04-17T08:10:28Z","file_size":2072197,"creator":"dernst","date_created":"2023-04-17T08:10:28Z","file_name":"2022_DMTCS_Biniaz.pdf"}],"language":[{"iso":"eng"}],"article_number":"9","author":[{"first_name":"Ahmad","last_name":"Biniaz","full_name":"Biniaz, Ahmad"},{"first_name":"Kshitij","last_name":"Jain","full_name":"Jain, Kshitij"},{"first_name":"Anna","last_name":"Lubiw","full_name":"Lubiw, Anna"},{"last_name":"Masárová","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana"},{"first_name":"Tillmann","full_name":"Miltzow, Tillmann","last_name":"Miltzow"},{"last_name":"Mondal","full_name":"Mondal, Debajyoti","first_name":"Debajyoti"},{"first_name":"Anurag Murty","full_name":"Naredla, Anurag Murty","last_name":"Naredla"},{"last_name":"Tkadlec","full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef"},{"first_name":"Alexi","full_name":"Turcotte, Alexi","last_name":"Turcotte"}],"article_processing_charge":"No","external_id":{"arxiv":["1903.06981"]},"title":"Token swapping on trees","citation":{"ieee":"A. Biniaz et al., “Token swapping on trees,” Discrete Mathematics and Theoretical Computer Science, vol. 24, no. 2. EPI Sciences, 2023.","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).","ama":"Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. Discrete Mathematics and Theoretical Computer Science. 2023;24(2). doi:10.46298/DMTCS.8383","apa":"Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte, A. (2023). Token swapping on trees. Discrete Mathematics and Theoretical Computer Science. EPI Sciences. https://doi.org/10.46298/DMTCS.8383","mla":"Biniaz, Ahmad, et al. “Token Swapping on Trees.” Discrete Mathematics and Theoretical Computer Science, vol. 24, no. 2, 9, EPI Sciences, 2023, doi:10.46298/DMTCS.8383.","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.","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.” Discrete Mathematics and Theoretical Computer Science. EPI Sciences, 2023. https://doi.org/10.46298/DMTCS.8383."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","publisher":"EPI Sciences","oa":1,"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","doi":"10.46298/DMTCS.8383","date_published":"2023-01-18T00:00:00Z","date_created":"2023-04-16T22:01:08Z","has_accepted_license":"1","year":"2023","day":"18","publication":"Discrete Mathematics and Theoretical Computer Science"},{"oa_version":"Published Version","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"}],"intvolume":" 26","month":"06","scopus_import":"1","language":[{"iso":"eng"}],"file":[{"success":1,"checksum":"dc6e255e3558faff924fd9e370886c11","file_id":"11940","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_name":"2022_JourGraphAlgorithmsApplic_Aichholzer.pdf","date_created":"2022-08-22T06:42:42Z","file_size":694538,"date_updated":"2022-08-22T06:42:42Z","creator":"dernst"}],"publication_status":"published","publication_identifier":{"issn":["1526-1719"]},"ec_funded":1,"issue":"2","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"9296"}]},"volume":26,"_id":"11938","status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article","article_type":"original","ddc":["000"],"date_updated":"2023-02-23T13:54:21Z","department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"file_date_updated":"2022-08-22T06:42:42Z","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).","oa":1,"quality_controlled":"1","publisher":"Brown University","publication":"Journal of Graph Algorithms and Applications","day":"01","year":"2022","has_accepted_license":"1","date_created":"2022-08-21T22:01:56Z","doi":"10.7155/jgaa.00591","date_published":"2022-06-01T00:00:00Z","page":"225-240","project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"name":"The Wittgenstein Prize","grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"name":"Game Theory","grant_number":"S11407","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Aichholzer, Oswin, et al. “On Compatible Matchings.” Journal of Graph Algorithms and Applications, vol. 26, no. 2, Brown University, 2022, pp. 225–40, doi:10.7155/jgaa.00591.","ieee":"O. Aichholzer et al., “On compatible matchings,” Journal of Graph Algorithms and Applications, 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.","apa":"Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2022). On compatible matchings. Journal of Graph Algorithms and Applications. Brown University. https://doi.org/10.7155/jgaa.00591","ama":"Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. Journal of Graph Algorithms and Applications. 2022;26(2):225-240. doi:10.7155/jgaa.00591","chicago":"Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible Matchings.” Journal of Graph Algorithms and Applications. Brown University, 2022. https://doi.org/10.7155/jgaa.00591.","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."},"title":"On compatible matchings","article_processing_charge":"No","external_id":{"arxiv":["2101.03928"]},"author":[{"last_name":"Aichholzer","full_name":"Aichholzer, Oswin","first_name":"Oswin"},{"first_name":"Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","last_name":"Arroyo Guevara","full_name":"Arroyo Guevara, Alan M","orcid":"0000-0003-2401-8670"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","last_name":"Masárová"},{"first_name":"Irene","last_name":"Parada","full_name":"Parada, Irene"},{"full_name":"Perz, Daniel","last_name":"Perz","first_name":"Daniel"},{"last_name":"Pilz","full_name":"Pilz, Alexander","first_name":"Alexander"},{"full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684","last_name":"Tkadlec","first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Vogtenhuber, Birgit","last_name":"Vogtenhuber","first_name":"Birgit"}]},{"project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z00342","name":"The Wittgenstein Prize"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"external_id":{"arxiv":["2101.03928"]},"article_processing_charge":"No","author":[{"last_name":"Aichholzer","full_name":"Aichholzer, Oswin","first_name":"Oswin"},{"first_name":"Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","last_name":"Arroyo Guevara","orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","last_name":"Masárová"},{"last_name":"Parada","full_name":"Parada, Irene","first_name":"Irene"},{"first_name":"Daniel","full_name":"Perz, Daniel","last_name":"Perz"},{"first_name":"Alexander","last_name":"Pilz","full_name":"Pilz, Alexander"},{"first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef"},{"first_name":"Birgit","full_name":"Vogtenhuber, Birgit","last_name":"Vogtenhuber"}],"title":"On compatible matchings","citation":{"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 15th International Conference on Algorithms and Computation, 12635:221–33. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-68211-8_18.","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.","mla":"Aichholzer, Oswin, et al. “On Compatible Matchings.” 15th International Conference on Algorithms and Computation, vol. 12635, Springer Nature, 2021, pp. 221–33, doi:10.1007/978-3-030-68211-8_18.","apa":"Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2021). On compatible matchings. In 15th International Conference on Algorithms and Computation (Vol. 12635, pp. 221–233). Yangon, Myanmar: Springer Nature. https://doi.org/10.1007/978-3-030-68211-8_18","ama":"Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. In: 15th International Conference on Algorithms and Computation. Vol 12635. Springer Nature; 2021:221-233. doi:10.1007/978-3-030-68211-8_18","ieee":"O. Aichholzer et al., “On compatible matchings,” in 15th International Conference on Algorithms and Computation, 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."},"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","oa":1,"quality_controlled":"1","publisher":"Springer Nature","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).","page":"221-233","date_created":"2021-03-28T22:01:41Z","doi":"10.1007/978-3-030-68211-8_18","date_published":"2021-02-16T00:00:00Z","year":"2021","publication":"15th International Conference on Algorithms and Computation","day":"16","conference":{"start_date":"2021-02-28","location":"Yangon, Myanmar","end_date":"2021-03-02","name":"WALCOM: Algorithms and Computation"},"type":"conference","status":"public","_id":"9296","department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"date_updated":"2023-02-21T16:33:44Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2101.03928"}],"alternative_title":["LNCS"],"scopus_import":"1","intvolume":" 12635","month":"02","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."}],"oa_version":"Preprint","ec_funded":1,"volume":12635,"related_material":{"record":[{"status":"public","id":"11938","relation":"later_version"}]},"publication_status":"published","publication_identifier":{"eissn":["16113349"],"isbn":["9783030682101"],"issn":["03029743"]},"language":[{"iso":"eng"}]},{"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1910.09917v3"}],"month":"02","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."}],"oa_version":"Preprint","volume":93,"related_material":{"record":[{"id":"6989","status":"public","relation":"shorter_version"}]},"publication_identifier":{"issn":["09257721"]},"publication_status":"published","language":[{"iso":"eng"}],"type":"journal_article","article_type":"original","status":"public","_id":"8317","department":[{"_id":"HeEd"}],"date_updated":"2023-08-04T10:57:42Z","quality_controlled":"1","publisher":"Elsevier","oa":1,"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","date_created":"2020-08-30T22:01:09Z","isi":1,"year":"2021","day":"01","publication":"Computational Geometry: Theory and Applications","project":[{"name":"The Wittgenstein Prize","grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"article_number":"101700","author":[{"last_name":"Aichholzer","full_name":"Aichholzer, Oswin","first_name":"Oswin"},{"first_name":"Hugo A.","full_name":"Akitaya, Hugo A.","last_name":"Akitaya"},{"first_name":"Kenneth C.","last_name":"Cheung","full_name":"Cheung, Kenneth C."},{"first_name":"Erik D.","full_name":"Demaine, Erik D.","last_name":"Demaine"},{"last_name":"Demaine","full_name":"Demaine, Martin L.","first_name":"Martin L."},{"first_name":"Sándor P.","full_name":"Fekete, Sándor P.","last_name":"Fekete"},{"full_name":"Kleist, Linda","last_name":"Kleist","first_name":"Linda"},{"last_name":"Kostitsyna","full_name":"Kostitsyna, Irina","first_name":"Irina"},{"first_name":"Maarten","full_name":"Löffler, Maarten","last_name":"Löffler"},{"last_name":"Masárová","orcid":"0000-0002-6660-1322","full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana"},{"full_name":"Mundilova, Klara","last_name":"Mundilova","first_name":"Klara"},{"last_name":"Schmidt","full_name":"Schmidt, Christiane","first_name":"Christiane"}],"article_processing_charge":"No","external_id":{"isi":["000579185100004"],"arxiv":["1910.09917"]},"title":"Folding polyominoes with holes into a cube","citation":{"mla":"Aichholzer, Oswin, et al. “Folding Polyominoes with Holes into a Cube.” Computational Geometry: Theory and Applications, vol. 93, 101700, Elsevier, 2021, doi:10.1016/j.comgeo.2020.101700.","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. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2020.101700","ama":"Aichholzer O, Akitaya HA, Cheung KC, et al. Folding polyominoes with holes into a cube. Computational Geometry: Theory and Applications. 2021;93. doi:10.1016/j.comgeo.2020.101700","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).","ieee":"O. Aichholzer et al., “Folding polyominoes with holes into a cube,” Computational Geometry: Theory and Applications, vol. 93. Elsevier, 2021.","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.” Computational Geometry: Theory and Applications. Elsevier, 2021. https://doi.org/10.1016/j.comgeo.2020.101700.","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."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8"},{"department":[{"_id":"HeEd"},{"_id":"UlWa"}],"file_date_updated":"2020-07-14T12:48:05Z","ddc":["516","514"],"date_updated":"2023-09-07T13:17:37Z","supervisor":[{"first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","last_name":"Wagner"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833"}],"keyword":["reconfiguration","reconfiguration graph","triangulations","flip","constrained triangulations","shellability","piecewise-linear balls","token swapping","trees","coloured weighted token swapping"],"status":"public","tmp":{"short":"CC BY-SA (4.0)","image":"/images/cc_by_sa.png","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)"},"type":"dissertation","_id":"7944","license":"https://creativecommons.org/licenses/by-sa/4.0/","related_material":{"record":[{"status":"public","id":"7950","relation":"part_of_dissertation"},{"id":"5986","status":"public","relation":"part_of_dissertation"}]},"language":[{"iso":"eng"}],"file":[{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_id":"7945","checksum":"df688bc5a82b50baee0b99d25fc7b7f0","creator":"zmasarov","file_size":13661779,"date_updated":"2020-07-14T12:48:05Z","file_name":"THESIS_Zuzka_Masarova.pdf","date_created":"2020-06-08T00:34:00Z"},{"relation":"source_file","access_level":"closed","content_type":"application/zip","file_id":"7946","checksum":"45341a35b8f5529c74010b7af43ac188","creator":"zmasarov","file_size":32184006,"date_updated":"2020-07-14T12:48:05Z","file_name":"THESIS_Zuzka_Masarova_SOURCE_FILES.zip","date_created":"2020-06-08T00:35:30Z"}],"degree_awarded":"PhD","publication_status":"published","publication_identifier":{"issn":["2663-337X"],"isbn":["978-3-99078-005-3"]},"month":"06","alternative_title":["ISTA Thesis"],"oa_version":"Published Version","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."}],"title":"Reconfiguration problems","article_processing_charge":"No","author":[{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","last_name":"Masárová"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"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. https://doi.org/10.15479/AT:ISTA:7944.","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:10.15479/AT:ISTA:7944","apa":"Masárová, Z. (2020). Reconfiguration problems. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:7944","mla":"Masárová, Zuzana. Reconfiguration Problems. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7944."},"date_created":"2020-06-08T00:49:46Z","doi":"10.15479/AT:ISTA:7944","date_published":"2020-06-09T00:00:00Z","page":"160","day":"09","year":"2020","has_accepted_license":"1","oa":1,"publisher":"Institute of Science and Technology Austria"},{"department":[{"_id":"HeEd"}],"title":"Folding polyominoes with holes into a cube","external_id":{"arxiv":["1910.09917"]},"article_processing_charge":"No","author":[{"first_name":"Oswin","last_name":"Aichholzer","full_name":"Aichholzer, Oswin"},{"first_name":"Hugo A","full_name":"Akitaya, Hugo A","last_name":"Akitaya"},{"first_name":"Kenneth C","full_name":"Cheung, Kenneth C","last_name":"Cheung"},{"first_name":"Erik D","full_name":"Demaine, Erik D","last_name":"Demaine"},{"last_name":"Demaine","full_name":"Demaine, Martin L","first_name":"Martin L"},{"full_name":"Fekete, Sandor P","last_name":"Fekete","first_name":"Sandor 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"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","orcid":"0000-0002-6660-1322","full_name":"Masárová, Zuzana","last_name":"Masárová"},{"first_name":"Klara","last_name":"Mundilova","full_name":"Mundilova, Klara"},{"last_name":"Schmidt","full_name":"Schmidt, Christiane","first_name":"Christiane"}],"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","date_updated":"2023-08-04T10:57:42Z","citation":{"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 Proceedings of the 31st Canadian Conference on Computational Geometry, 164–70. Canadian Conference on Computational Geometry, 2019.","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.","mla":"Aichholzer, Oswin, et al. “Folding Polyominoes with Holes into a Cube.” Proceedings of the 31st Canadian Conference on Computational Geometry, Canadian Conference on Computational Geometry, 2019, pp. 164–70.","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 Proceedings of the 31st Canadian Conference on Computational Geometry (pp. 164–170). Edmonton, Canada: Canadian Conference on Computational Geometry.","ama":"Aichholzer O, Akitaya HA, Cheung KC, et al. Folding polyominoes with holes into a cube. In: Proceedings of the 31st Canadian Conference on Computational Geometry. Canadian Conference on Computational Geometry; 2019:164-170.","ieee":"O. Aichholzer et al., “Folding polyominoes with holes into a cube,” in Proceedings of the 31st Canadian Conference on Computational Geometry, 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."},"status":"public","conference":{"location":"Edmonton, Canada","end_date":"2019-08-10","start_date":"2019-08-08","name":"CCCG: Canadian Conference in Computational Geometry"},"type":"conference","_id":"6989","date_created":"2019-11-04T16:46:11Z","related_material":{"record":[{"id":"8317","status":"public","relation":"extended_version"}]},"date_published":"2019-08-01T00:00:00Z","page":"164-170","publication":"Proceedings of the 31st Canadian Conference on Computational Geometry","language":[{"iso":"eng"}],"day":"01","publication_status":"published","year":"2019","month":"08","oa":1,"main_file_link":[{"open_access":"1","url":"https://cccg.ca/proceedings/2019/proceedings.pdf"}],"publisher":"Canadian Conference on Computational Geometry","quality_controlled":"1","scopus_import":"1","acknowledgement":"This research was performed in part at the 33rd BellairsWinter Workshop on Computational Geometry. Wethank all other participants for a fruitful atmosphere.","oa_version":"Published Version","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"}]},{"related_material":{"record":[{"status":"public","id":"683","relation":"earlier_version"},{"id":"7944","status":"public","relation":"dissertation_contains"}]},"issue":"4","volume":61,"language":[{"iso":"eng"}],"file":[{"file_name":"2018_DiscreteGeometry_Lubiw.pdf","date_created":"2019-02-14T11:57:22Z","creator":"dernst","file_size":556276,"date_updated":"2020-07-14T12:47:14Z","checksum":"e1bff88f1d77001b53b78c485ce048d7","file_id":"5988","relation":"main_file","access_level":"open_access","content_type":"application/pdf"}],"publication_status":"published","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"intvolume":" 61","month":"06","scopus_import":"1","oa_version":"Published Version","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"}],"department":[{"_id":"UlWa"}],"file_date_updated":"2020-07-14T12:47:14Z","ddc":["000"],"date_updated":"2023-09-07T13:17:36Z","status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","type":"journal_article","_id":"5986","date_created":"2019-02-14T11:54:08Z","date_published":"2019-06-01T00:00:00Z","doi":"10.1007/s00454-018-0035-8","page":"880-898","publication":"Discrete & Computational Geometry","day":"01","year":"2019","isi":1,"has_accepted_license":"1","oa":1,"publisher":"Springer Nature","quality_controlled":"1","title":"A proof of the orbit conjecture for flipping edge-labelled triangulations","article_processing_charge":"Yes (via OA deal)","external_id":{"arxiv":["1710.02741"],"isi":["000466130000009"]},"author":[{"first_name":"Anna","last_name":"Lubiw","full_name":"Lubiw, Anna"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","last_name":"Masárová","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322"},{"last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"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.","chicago":"Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” Discrete & Computational Geometry. Springer Nature, 2019. https://doi.org/10.1007/s00454-018-0035-8.","ieee":"A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for flipping edge-labelled triangulations,” Discrete & Computational Geometry, vol. 61, no. 4. Springer Nature, pp. 880–898, 2019.","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. Springer Nature. https://doi.org/10.1007/s00454-018-0035-8","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","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."},"project":[{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}]},{"publication_status":"submitted","year":"2019","day":"16","language":[{"iso":"eng"}],"publication":"arXiv","date_published":"2019-03-16T00:00:00Z","related_material":{"record":[{"id":"7944","status":"public","relation":"dissertation_contains"},{"relation":"later_version","id":"12833","status":"public"}]},"date_created":"2020-06-08T12:25:25Z","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"}],"oa_version":"Preprint","main_file_link":[{"url":"https://arxiv.org/abs/1903.06981","open_access":"1"}],"oa":1,"month":"03","date_updated":"2024-01-04T12:42:08Z","citation":{"ieee":"A. Biniaz et al., “Token swapping on trees,” arXiv. .","short":"A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec, A. Turcotte, ArXiv (n.d.).","apa":"Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte, A. (n.d.). Token swapping on trees. arXiv.","ama":"Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. arXiv.","mla":"Biniaz, Ahmad, et al. “Token Swapping on Trees.” ArXiv, 1903.06981.","ista":"Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec J, Turcotte A. Token swapping on trees. arXiv, 1903.06981.","chicago":"Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token Swapping on Trees.” ArXiv, n.d."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Biniaz, Ahmad","last_name":"Biniaz","first_name":"Ahmad"},{"first_name":"Kshitij","full_name":"Jain, Kshitij","last_name":"Jain"},{"first_name":"Anna","full_name":"Lubiw, Anna","last_name":"Lubiw"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","last_name":"Masárová","orcid":"0000-0002-6660-1322","full_name":"Masárová, Zuzana"},{"first_name":"Tillmann","last_name":"Miltzow","full_name":"Miltzow, Tillmann"},{"full_name":"Mondal, Debajyoti","last_name":"Mondal","first_name":"Debajyoti"},{"full_name":"Naredla, Anurag Murty","last_name":"Naredla","first_name":"Anurag Murty"},{"id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef","full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684","last_name":"Tkadlec"},{"last_name":"Turcotte","full_name":"Turcotte, Alexi","first_name":"Alexi"}],"external_id":{"arxiv":["1903.06981"]},"article_processing_charge":"No","department":[{"_id":"HeEd"},{"_id":"UlWa"},{"_id":"KrCh"}],"title":"Token swapping on trees","_id":"7950","article_number":"1903.06981","type":"preprint","status":"public"},{"file":[{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","checksum":"24fdde981cc513352a78dcf9b0660ae9","file_id":"5265","creator":"system","file_size":710007,"date_updated":"2020-07-14T12:47:41Z","file_name":"IST-2017-896-v1+1_LIPIcs-SoCG-2017-49.pdf","date_created":"2018-12-12T10:17:12Z"}],"language":[{"iso":"eng"}],"publication_status":"published","volume":77,"related_material":{"record":[{"relation":"later_version","status":"public","id":"5986"}]},"oa_version":"Published Version","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"}],"month":"06","intvolume":" 77","scopus_import":1,"alternative_title":["LIPIcs"],"ddc":["514","516"],"date_updated":"2023-09-05T15:01:43Z","department":[{"_id":"UlWa"}],"file_date_updated":"2020-07-14T12:47:41Z","_id":"683","status":"public","pubrep_id":"896","type":"conference","conference":{"start_date":"2017-07-04","end_date":"2017-07-07","location":"Brisbane, Australia","name":"SoCG: Symposium on Computational Geometry"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"day":"01","has_accepted_license":"1","year":"2017","doi":"10.4230/LIPIcs.SoCG.2017.49","date_published":"2017-06-01T00:00:00Z","date_created":"2018-12-11T11:47:54Z","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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.","apa":"Lubiw, A., Masárová, Z., & Wagner, U. (2017). A proof of the orbit conjecture for flipping edge labelled triangulations (Vol. 77). Presented at the SoCG: Symposium on Computational Geometry, Brisbane, Australia: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2017.49","ama":"Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping edge labelled triangulations. In: Vol 77. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.SoCG.2017.49","mla":"Lubiw, Anna, et al. A Proof of the Orbit Conjecture for Flipping Edge Labelled Triangulations. Vol. 77, 49, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.SoCG.2017.49.","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.","chicago":"Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture for Flipping Edge Labelled Triangulations,” Vol. 77. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.SoCG.2017.49."},"title":"A proof of the orbit conjecture for flipping edge labelled triangulations","publist_id":"7033","author":[{"last_name":"Lubiw","full_name":"Lubiw, Anna","first_name":"Anna"},{"first_name":"Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322","full_name":"Masárová, Zuzana","last_name":"Masárová"},{"orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli"}],"article_number":"49"}]