Tightening nonsimple paths and cycles on surfaces

Éric Colin De Verdière, Jeff Erickson

Research output: Contribution to journalArticlepeer-review

Abstract

We describe algorithms to compute the shortest path homotopic to a given path, or the shortest cycle freely homotopic to a given cycle, on an orientable combinatorial surface. Unlike earlier results, our algorithms do not require the input path or cycle to be simple. Given a surface with complexity n, genus g ≥ 2, and no boundary, we construct in O(gn log n) time a tight octagonal decomposition of the surface-A set of simple cycles, each as short as possible in its free homotopy class, that decompose the surface into a complex of octagons meeting four at a vertex. After the surface is preprocessed, we can compute the shortest path homotopic to a given path of complexity k in O(gnk) time, or the shortest cycle homotopic to a given cycle of complexity k in O(gnk log(nk)) time. A similar algorithm computes shortest homotopic curves on surfaces with boundary or with genus 1. We also prove that the recent algorithms of Colin de Verdiére and Lazarus for shortening embedded graphs and sets of cycles have running times polynomial in the complexity of the surface and the input curves, regardless of the surface geometry.

Original languageEnglish (US)
Pages (from-to)3784-3813
Number of pages30
JournalSIAM Journal on Computing
Volume39
Issue number8
DOIs
StatePublished - 2010

Keywords

  • Combinatorial surface
  • Computational topology
  • Embedded graph
  • Homotopy
  • Topological graph theory

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Tightening nonsimple paths and cycles on surfaces'. Together they form a unique fingerprint.

Cite this