Chang, HsienChih ;
Erickson, Jeff
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 selfcrossings 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}) degree1 reductions, seriesparallel reductions, and DeltaY 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 noncontractible closed curve on the torus to another; this lower bound is tight if the curve is homotopic to a simple closed curve.
BibTeX  Entry
@InProceedings{chang_et_al:LIPIcs:2016:5921,
author = {HsienChih Chang and Jeff Erickson},
title = {{Untangling Planar Curves}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {29:129:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770095},
ISSN = {18688969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5921},
URN = {urn:nbn:de:0030drops59218},
doi = {10.4230/LIPIcs.SoCG.2016.29},
annote = {Keywords: computational topology, homotopy, planar graphs, DeltaY transformations, defect, Reidemeister moves, tangles}
}
2016
Keywords: 

computational topology, homotopy, planar graphs, DeltaY transformations, defect, Reidemeister moves, tangles 
Seminar: 

32nd International Symposium on Computational Geometry (SoCG 2016)

Issue date: 

2016 
Date of publication: 

2016 