Untangling planar curves

Hsien Chih Chang, Jeff Erickson

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 Θ(n3/2) homotopy moves in the worst case. Our algorithm improves the best previous upper bound O(n2), 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 Ω(n3/2) degree-1 reductions, series-parallel reductions, and ΔY transformations are required to reduce any planar graph with treewidth Ω(√n) to a single edge, matching known upper bounds for rectangular and cylindrical grid graphs. Finally, we prove that Ω(n2) 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.

Original languageEnglish (US)
Title of host publication32nd International Symposium on Computational Geometry, SoCG 2016
EditorsSandor Fekete, Anna Lubiw
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770095
StatePublished - Jun 1 2016
Event32nd International Symposium on Computational Geometry, SoCG 2016 - Boston, United States
Duration: Jun 14 2016Jun 17 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other32nd International Symposium on Computational Geometry, SoCG 2016
Country/TerritoryUnited States


  • Computational topology
  • Defect
  • Homotopy
  • Planar graphs
  • Reidemeister moves
  • Tangles
  • ΔY transformations

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Untangling planar curves'. Together they form a unique fingerprint.

Cite this