Untangling Planar Curves

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 \(\Theta (n^{3/2})\) homotopy moves in the worst case. Our algorithm improves the best previous upper bound \(O(n^2)\), 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. Our lower bound also implies that \(\Omega (n^{3/2})\) facial electrical transformations are required to reduce any plane graph with treewidth \(\Omega (\sqrt{n})\) to a single vertex, matching known upper bounds for rectangular and cylindrical grid graphs. More generally, we prove that transforming one immersion of k circles with at most n self-crossings into another requires \(\Theta (n^{3/2} + nk + k^2)\) homotopy moves in the worst case. Finally, we prove that transforming one non-contractible closed curve to another on any orientable surface requires \(\Omega (n^2)\) homotopy moves in the worst case; this lower bound is tight if the curve is homotopic to a simple closed curve.