@inproceedings{cd9415fbf3a94e3dacc23cac71b9c660,

title = "Untangling planar curves",

abstract = "Any generic closed curve in the plane can be transformed into a simple closed curve by a finite sequence of local transformations called homotopy moves. We prove that simplifying a planar closed curve with n self-crossings requires Θ(n3/2) homotopy moves in the worst case. Our algorithm improves the best previous upper bound O(n2), which is already implicit in the classical work of Steinitz; the matching lower bound follows from the construction of closed curves with large defect, a topological invariant of generic closed curves introduced by Aicardi and Arnold. This lower bound also implies that Ω(n3/2) degree-1 reductions, series-parallel reductions, and ΔY transformations are required to reduce any planar graph with treewidth Ω(√n) to a single edge, matching known upper bounds for rectangular and cylindrical grid graphs. Finally, we prove that Ω(n2) homotopy moves are required in the worst case to transform one non-contractible closed curve on the torus to another; this lower bound is tight if the curve is homotopic to a simple closed curve.",

keywords = "Computational topology, Defect, Homotopy, Planar graphs, Reidemeister moves, Tangles, ΔY transformations",

author = "Chang, {Hsien Chih} and Jeff Erickson",

note = "Funding Information: Work on this paper was partially supported by NSF grant CCF-1408763. See http://jeffe.cs.illinois.edu/pubs/tangle.pdf for the most recent version of this paper. Publisher Copyright: {\textcopyright} Hsien-Chih Chang and Jeff Erickson.; 32nd International Symposium on Computational Geometry, SoCG 2016 ; Conference date: 14-06-2016 Through 17-06-2016",

year = "2016",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.SoCG.2016.29",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "29.1--29.16",

editor = "Sandor Fekete and Anna Lubiw",

booktitle = "32nd International Symposium on Computational Geometry, SoCG 2016",

}