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