Untangling planar curves

DOI10.4230/LIPICS.SOCG.2016.29zbMATH Open1387.57028arXiv1702.00146OpenAlexW2461895470MaRDI QIDQ3132863FDOQ3132863

Hsien-Chih Chang, Jeff Erickson

Publication date: 30 January 2018

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(sqrtn)$ 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.

Full work available at URL: https://arxiv.org/abs/1702.00146

Recommendations

• Untangling planar curves
• Untangling two systems of noncrossing curves
• scientific article; zbMATH DE number 6850316
• Complexity of plane and spherical curves
• Untangling two systems of noncrossing curves

zbMATH Keywords

computational topologydefecthomotopyplanar graphstanglesReidemeister movesDelta-Y transformations

Mathematics Subject Classification ID

General geometric structures on low-dimensional manifolds (57M50) Relations of low-dimensional topology with graph theory (57M15)

Cited In (8)

• Complexity of geodesics on 2-dimensional ideal polyhedra and isotopies
• Coaxing a planar curve to comply
• Title not available (Why is that?)
• Untangling a polygon
• Lower bounds for electrical reduction on surfaces
• Determining the orientation of closed planar curves
• Untangling planar curves
• On the Number of Unknot Diagrams

This page was built for publication: Untangling planar curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3132863)