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
$\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
noncontractible 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.