Untangling planar curves

DOI10.4230/LIPICS.SOCG.2016.29MaRDI QIDQ3132863zbMATH OpenOpenAlexFDO

Authors Hsien-Chih Chang, Jeff Erickson

Publication date 30 January 2018

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

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)

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.

Recommendations

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

Cited in

(12)

• Complexity of geodesics on 2-dimensional ideal polyhedra and isotopies
• Coaxing a planar curve to comply
• scientific article; zbMATH DE number 4079447 (Why is no real title available?)
• Bringing closed polygonal curves in the plane to normal form via local moves
• Untangling a polygon
• Lower bounds for electrical reduction on surfaces
• On the number of unknot diagrams
• Converting homotopies to isotopies and dividing homotopies in half in an effective way
• Complexity of plane and spherical curves
• Tightening Curves on Surfaces Monotonically with Applications
• Determining the orientation of closed planar curves
• Untangling planar curves

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)