Untangling Planar Curves

Hsien Chih Chang, Jeff Erickson

Research output: Contribution to journalArticlepeer-review

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 Θ (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. Our lower bound also implies that Ω (n3 / 2) facial electrical transformations are required to reduce any plane graph with treewidth Ω(n) 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 Θ (n3 / 2+ nk+ k2) homotopy moves in the worst case. Finally, we prove that transforming one non-contractible closed curve to another on any orientable surface requires Ω (n2) homotopy moves in the worst case; this lower bound is tight if the curve is homotopic to a simple closed curve.

Original languageEnglish (US)
Pages (from-to)889-920
Number of pages32
JournalDiscrete and Computational Geometry
Volume58
Issue number4
DOIs
StatePublished - Dec 1 2017

Keywords

  • Curve invariants
  • Curves on surfaces
  • Homotopy
  • Planar graphs
  • Δ Y transformations

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Untangling Planar Curves'. Together they form a unique fingerprint.

Cite this