Untangling planar curves

With Hsien-Chih Chang*.

To appear in Discrete & Computational Geometry, 2017.
(special issue of invited papers from the 32nd International Symposium on Computational Geometry)


Proceedings of the 32nd International Symposium on Computational Geometry, 29:1--29:16, 2016.
Winner of the SoCG 2016 Best Student Presentation award.

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(n²), 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 introduced by Aicardi and Arnold. This lower bound also implies that Ω(n3/2) facial electrical 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. More generally, we prove that transforming one immersion of k circles with at most n self-crossings into another requires Θ(n3/2 + nk + k²) homotopy moves in the worst case. Finally, we prove that Ω(n²) 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.

Publications - Jeff Erickson (jeffe@illinois.edu) 16 Aug 2017