2026-07-23T20:31:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5921 2024-03-06T10:37:17Z ddc:004 open_access

Untangling Planar Curves Chang, Hsien-Chih Erickson, Jeff computational topology homotopy planar graphs Delta-Y transformations defect Reidemeister moves tangles 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. This lower bound also implies that Omega(n^{3/2}) degree-1 reductions, series-parallel reductions, and Delta-Y transformations are required to reduce any planar graph with treewidth Omega(sqrt{n}) to a single edge, matching known upper bounds for rectangular and cylindrical grid graphs. Finally, we prove that Omega(n^2) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hsien-Chih Chang and Jeff Erickson 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.29 urn:nbn:de:0030-drops-59218 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.29 eng https://creativecommons.org/licenses/by/3.0/legalcode