## 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 Θ (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 Ω (n^{3 / 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 Θ (n^{3 / 2}+ nk+ k^{2}) homotopy moves in the worst case. Finally, we prove that transforming one non-contractible closed curve to another on any orientable surface requires Ω (n^{2}) homotopy moves in the worst case; this lower bound is tight if the curve is homotopic to a simple closed curve.

Original language | English (US) |
---|---|

Pages (from-to) | 889-920 |

Number of pages | 32 |

Journal | Discrete and Computational Geometry |

Volume | 58 |

Issue number | 4 |

DOIs | |

State | Published - 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