[{"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1910.09917v3"}],"publisher":"Elsevier","project":[{"_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"The Wittgenstein Prize","grant_number":"Z00342"}],"month":"02","date_updated":"2021-06-29T09:37:49Z","intvolume":" 93","oa_version":"Preprint","status":"public","publication":"Computational Geometry: Theory and Applications","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"8317","title":"Folding polyominoes with holes into a cube","year":"2021","oa":1,"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 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.","lang":"eng"}],"quality_controlled":"1","date_published":"2021-02-01T00:00:00Z","department":[{"_id":"HeEd"}],"day":"01","date_created":"2020-08-30T22:01:09Z","language":[{"iso":"eng"}],"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","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).","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.","ieee":"O. Aichholzer *et al.*, “Folding polyominoes with holes into a cube,” *Computational Geometry: Theory and Applications*, vol. 93. Elsevier, 2021.","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.","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"},"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.","related_material":{"record":[{"relation":"shorter_version","id":"6989","status":"public"}]},"publication_identifier":{"issn":["09257721"]},"type":"journal_article","external_id":{"arxiv":["1910.09917"]},"publication_status":"published","scopus_import":"1","author":[{"first_name":"Oswin","last_name":"Aichholzer","full_name":"Aichholzer, Oswin"},{"full_name":"Akitaya, Hugo A.","last_name":"Akitaya","first_name":"Hugo A."},{"first_name":"Kenneth C.","last_name":"Cheung","full_name":"Cheung, Kenneth C."},{"full_name":"Demaine, Erik D.","first_name":"Erik D.","last_name":"Demaine"},{"first_name":"Martin L.","last_name":"Demaine","full_name":"Demaine, Martin L."},{"last_name":"Fekete","first_name":"Sándor P.","full_name":"Fekete, Sándor P."},{"first_name":"Linda","last_name":"Kleist","full_name":"Kleist, Linda"},{"full_name":"Kostitsyna, Irina","last_name":"Kostitsyna","first_name":"Irina"},{"last_name":"Löffler","first_name":"Maarten","full_name":"Löffler, Maarten"},{"last_name":"Masárová","first_name":"Zuzana","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Mundilova, Klara","first_name":"Klara","last_name":"Mundilova"},{"last_name":"Schmidt","first_name":"Christiane","full_name":"Schmidt, Christiane"}],"article_processing_charge":"No","doi":"10.1016/j.comgeo.2020.101700","volume":93,"article_type":"original","article_number":"101700"},{"project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"grant_number":"Z00342","name":"The Wittgenstein Prize","call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425"},{"_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","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"publisher":"Springer Nature","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2101.03928"}],"oa_version":"Preprint","date_updated":"2021-07-22T13:40:48Z","intvolume":" 12635","alternative_title":["LNCS"],"month":"02","_id":"9296","title":"On compatible matchings","oa":1,"year":"2021","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","status":"public","publication":"15th International Conference on Algorithms and Computation","quality_controlled":"1","conference":{"end_date":"2021-03-02","start_date":"2021-02-28","location":"Yangon, Myanmar","name":"WALCOM: Algorithms and Computation"},"abstract":[{"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.","lang":"eng"}],"day":"16","department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"date_published":"2021-02-16T00:00:00Z","page":"221-233","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).","type":"conference","publication_identifier":{"eissn":["16113349"],"isbn":["9783030682101"],"issn":["03029743"]},"language":[{"iso":"eng"}],"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.","ieee":"O. Aichholzer *et al.*, “On compatible matchings,” in *15th International Conference on Algorithms and Computation*, Yangon, Myanmar, 2021, vol. 12635, pp. 221–233.","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","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.","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.","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"},"date_created":"2021-03-28T22:01:41Z","ec_funded":1,"article_processing_charge":"No","publication_status":"published","scopus_import":"1","author":[{"last_name":"Aichholzer","first_name":"Oswin","full_name":"Aichholzer, Oswin"},{"id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","full_name":"Arroyo Guevara, Alan M","first_name":"Alan M","last_name":"Arroyo Guevara"},{"last_name":"Masárová","first_name":"Zuzana","full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322"},{"last_name":"Parada","first_name":"Irene","full_name":"Parada, Irene"},{"full_name":"Perz, Daniel","last_name":"Perz","first_name":"Daniel"},{"last_name":"Pilz","first_name":"Alexander","full_name":"Pilz, Alexander"},{"id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","first_name":"Josef","full_name":"Tkadlec, Josef"},{"full_name":"Vogtenhuber, Birgit","last_name":"Vogtenhuber","first_name":"Birgit"}],"external_id":{"arxiv":["2101.03928"]},"volume":12635,"doi":"10.1007/978-3-030-68211-8_18"},{"month":"06","file":[{"file_name":"THESIS_Zuzka_Masarova.pdf","access_level":"open_access","creator":"zmasarov","checksum":"df688bc5a82b50baee0b99d25fc7b7f0","relation":"main_file","file_id":"7945","date_updated":"2020-07-14T12:48:05Z","content_type":"application/pdf","date_created":"2020-06-08T00:34:00Z","file_size":13661779},{"file_name":"THESIS_Zuzka_Masarova_SOURCE_FILES.zip","access_level":"closed","creator":"zmasarov","checksum":"45341a35b8f5529c74010b7af43ac188","file_id":"7946","date_updated":"2020-07-14T12:48:05Z","relation":"source_file","content_type":"application/zip","date_created":"2020-06-08T00:35:30Z","file_size":32184006}],"alternative_title":["IST Austria Thesis"],"date_updated":"2021-01-12T08:16:11Z","oa_version":"Published Version","publisher":"IST Austria","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":{"name":"Creative Commons Attribution-ShareAlike 4.0 International Public License (CC BY-SA 4.0)","short":"CC BY-SA (4.0)","legal_code_url":"https://creativecommons.org/licenses/by-sa/4.0/legalcode","image":"/images/cc_by_sa.png"},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"year":"2020","_id":"7944","title":"Reconfiguration problems","supervisor":[{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli"},{"first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"keyword":["reconfiguration","reconfiguration graph","triangulations","flip","constrained triangulations","shellability","piecewise-linear balls","token swapping","trees","coloured weighted token swapping"],"date_created":"2020-06-08T00:49:46Z","citation":{"ista":"Masárová Z. 2020. Reconfiguration problems. IST Austria.","ama":"Masárová Z. Reconfiguration problems. 2020. doi:10.15479/AT:ISTA:7944","ieee":"Z. Masárová, “Reconfiguration problems,” IST Austria, 2020.","chicago":"Masárová, Zuzana. “Reconfiguration Problems.” IST Austria, 2020. https://doi.org/10.15479/AT:ISTA:7944.","apa":"Masárová, Z. (2020). *Reconfiguration problems*. IST Austria. https://doi.org/10.15479/AT:ISTA:7944","short":"Z. Masárová, Reconfiguration Problems, IST Austria, 2020.","mla":"Masárová, Zuzana. *Reconfiguration Problems*. IST Austria, 2020, doi:10.15479/AT:ISTA:7944."},"ddc":["516","514"],"language":[{"iso":"eng"}],"type":"dissertation","publication_identifier":{"isbn":["978-3-99078-005-3"],"eissn":["2663-337X"]},"page":"160","related_material":{"record":[{"relation":"part_of_dissertation","status":"public","id":"5986"},{"relation":"part_of_dissertation","status":"public","id":"7950"}]},"date_published":"2020-06-09T00:00:00Z","department":[{"_id":"HeEd"},{"_id":"UlWa"}],"license":"https://creativecommons.org/licenses/by-sa/4.0/","day":"09","doi":"10.15479/AT:ISTA:7944","has_accepted_license":"1","author":[{"full_name":"Masárová, Zuzana","first_name":"Zuzana","last_name":"Masárová","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322"}],"file_date_updated":"2020-07-14T12:48:05Z","publication_status":"published","article_processing_charge":"No"},{"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"}],"article_number":"1903.06981","publication_status":"submitted","author":[{"full_name":"Biniaz, Ahmad","last_name":"Biniaz","first_name":"Ahmad"},{"full_name":"Jain, Kshitij","first_name":"Kshitij","last_name":"Jain"},{"full_name":"Lubiw, Anna","last_name":"Lubiw","first_name":"Anna"},{"last_name":"Masárová","first_name":"Zuzana","full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322"},{"full_name":"Miltzow, Tillmann","first_name":"Tillmann","last_name":"Miltzow"},{"first_name":"Debajyoti","last_name":"Mondal","full_name":"Mondal, Debajyoti"},{"full_name":"Naredla, Anurag Murty","last_name":"Naredla","first_name":"Anurag Murty"},{"id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","full_name":"Tkadlec, Josef","first_name":"Josef","last_name":"Tkadlec"},{"full_name":"Turcotte, Alexi","first_name":"Alexi","last_name":"Turcotte"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","external_id":{"arxiv":["1903.06981"]},"publication":"arXiv","article_processing_charge":"No","_id":"7950","title":"Token swapping on trees","year":"2019","oa":1,"language":[{"iso":"eng"}],"citation":{"short":"A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec, A. Turcotte, ArXiv (n.d.).","apa":"Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte, A. (n.d.). Token swapping on trees. *arXiv*.","mla":"Biniaz, Ahmad, et al. “Token Swapping on Trees.” *ArXiv*, 1903.06981.","ama":"Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. *arXiv*.","ista":"Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec J, Turcotte A. Token swapping on trees. arXiv, 1903.06981.","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.","ieee":"A. Biniaz *et al.*, “Token swapping on trees,” *arXiv*. ."},"date_created":"2020-06-08T12:25:25Z","month":"03","oa_version":"Preprint","date_updated":"2021-01-12T08:16:11Z","related_material":{"record":[{"status":"public","id":"7944","relation":"dissertation_contains"}]},"type":"preprint","department":[{"_id":"HeEd"},{"_id":"UlWa"},{"_id":"KrCh"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1903.06981"}],"date_published":"2019-03-16T00:00:00Z","day":"16"},{"year":"2019","oa":1,"_id":"5986","title":"A proof of the orbit conjecture for flipping edge-labelled triangulations","publication":"Discrete & Computational Geometry","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","abstract":[{"lang":"eng","text":"Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm (with 𝑂(𝑛8) being a crude bound on the run-time) to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of 𝑂(𝑛7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture."}],"publisher":"Springer Nature","project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"intvolume":" 61","date_updated":"2021-01-12T08:16:09Z","oa_version":"Published Version","month":"06","file":[{"creator":"dernst","checksum":"e1bff88f1d77001b53b78c485ce048d7","file_name":"2018_DiscreteGeometry_Lubiw.pdf","access_level":"open_access","date_created":"2019-02-14T11:57:22Z","file_size":556276,"date_updated":"2020-07-14T12:47:14Z","file_id":"5988","relation":"main_file","content_type":"application/pdf"}],"article_processing_charge":"Yes (via OA deal)","external_id":{"arxiv":["1710.02741"]},"has_accepted_license":"1","author":[{"full_name":"Lubiw, Anna","last_name":"Lubiw","first_name":"Anna"},{"last_name":"Masárová","first_name":"Zuzana","full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","last_name":"Wagner","full_name":"Wagner, Uli"}],"file_date_updated":"2020-07-14T12:47:14Z","publication_status":"published","scopus_import":1,"doi":"10.1007/s00454-018-0035-8","article_type":"original","volume":61,"day":"01","issue":"4","date_published":"2019-06-01T00:00:00Z","department":[{"_id":"UlWa"}],"type":"journal_article","publication_identifier":{"issn":["0179-5376","1432-0444"]},"page":"880-898","related_material":{"record":[{"relation":"earlier_version","id":"683","status":"public"},{"relation":"dissertation_contains","id":"7944","status":"public"}]},"date_created":"2019-02-14T11:54:08Z","citation":{"short":"A. Lubiw, Z. Masárová, U. Wagner, Discrete & Computational Geometry 61 (2019) 880–898.","apa":"Lubiw, A., Masárová, Z., & Wagner, U. (2019). A proof of the orbit conjecture for flipping edge-labelled triangulations. *Discrete & Computational Geometry*. Springer Nature. https://doi.org/10.1007/s00454-018-0035-8","mla":"Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” *Discrete & Computational Geometry*, vol. 61, no. 4, Springer Nature, 2019, pp. 880–98, doi:10.1007/s00454-018-0035-8.","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","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."},"ddc":["000"],"language":[{"iso":"eng"}]},{"quality_controlled":"1","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 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. "}],"conference":{"name":"CCCG: Canadian Conference in Computational Geometry","location":"Edmonton, Canada","start_date":"2019-08-08","end_date":"2019-08-10"},"article_processing_charge":"No","oa":1,"year":"2019","_id":"6989","title":"Folding polyominoes with holes into a cube","author":[{"full_name":"Aichholzer, Oswin","last_name":"Aichholzer","first_name":"Oswin"},{"full_name":"Akitaya, Hugo A","last_name":"Akitaya","first_name":"Hugo A"},{"last_name":"Cheung","first_name":"Kenneth C","full_name":"Cheung, Kenneth C"},{"last_name":"Demaine","first_name":"Erik D","full_name":"Demaine, Erik D"},{"full_name":"Demaine, Martin L","last_name":"Demaine","first_name":"Martin L"},{"last_name":"Fekete","first_name":"Sandor P","full_name":"Fekete, Sandor P"},{"first_name":"Linda","last_name":"Kleist","full_name":"Kleist, Linda"},{"full_name":"Kostitsyna, Irina","last_name":"Kostitsyna","first_name":"Irina"},{"first_name":"Maarten","last_name":"Löffler","full_name":"Löffler, Maarten"},{"first_name":"Zuzana","last_name":"Masárová","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Klara","last_name":"Mundilova","full_name":"Mundilova, Klara"},{"last_name":"Schmidt","first_name":"Christiane","full_name":"Schmidt, Christiane"}],"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","scopus_import":"1","publication_status":"published","publication":"Proceedings of the 31st Canadian Conference on Computational Geometry","external_id":{"arxiv":["1910.09917"]},"status":"public","oa_version":"Published Version","type":"conference","page":"164-170","acknowledgement":"This research was performed in part at the 33rd BellairsWinter Workshop on Computational Geometry. Wethank all other participants for a fruitful atmosphere.","date_updated":"2021-06-29T09:37:50Z","related_material":{"record":[{"status":"public","id":"8317","relation":"extended_version"}]},"citation":{"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.","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.","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.","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.","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.","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."},"language":[{"iso":"eng"}],"month":"08","date_created":"2019-11-04T16:46:11Z","day":"01","publisher":"Canadian Conference on Computational Geometry","main_file_link":[{"url":"https://cccg.ca/proceedings/2019/proceedings.pdf","open_access":"1"}],"department":[{"_id":"HeEd"}],"date_published":"2019-08-01T00:00:00Z"},{"has_accepted_license":"1","publication_status":"published","file_date_updated":"2020-07-14T12:47:41Z","scopus_import":1,"author":[{"full_name":"Lubiw, Anna","first_name":"Anna","last_name":"Lubiw"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322","last_name":"Masárová","first_name":"Zuzana","full_name":"Masárová, Zuzana"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner","full_name":"Wagner, Uli"}],"publist_id":"7033","article_number":"49","doi":"10.4230/LIPIcs.SoCG.2017.49","volume":77,"day":"01","date_published":"2017-06-01T00:00:00Z","department":[{"_id":"UlWa"}],"related_material":{"record":[{"status":"public","id":"5986","relation":"later_version"}]},"type":"conference","pubrep_id":"896","date_created":"2018-12-11T11:47:54Z","language":[{"iso":"eng"}],"ddc":["514","516"],"citation":{"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","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.","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","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.","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."},"_id":"683","title":"A proof of the orbit conjecture for flipping edge labelled triangulations","year":"2017","oa":1,"status":"public","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","conference":{"name":"SoCG: Symposium on Computational Geometry","location":"Brisbane, Australia","start_date":"2017-07-04","end_date":"2017-07-07"},"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"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_updated":"2021-01-12T08:09:13Z","alternative_title":["LIPIcs"],"intvolume":" 77","oa_version":"Published Version","month":"06","file":[{"file_name":"IST-2017-896-v1+1_LIPIcs-SoCG-2017-49.pdf","access_level":"open_access","creator":"system","checksum":"24fdde981cc513352a78dcf9b0660ae9","file_id":"5265","relation":"main_file","date_updated":"2020-07-14T12:47:41Z","content_type":"application/pdf","date_created":"2018-12-12T10:17:12Z","file_size":710007}]}]