Tightening non-simple paths and cycles on surfaces

Eric Colin De Verdière, Jeff Erickson

Research output: Contribution to conferencePaperpeer-review


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(n 2 logn) 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 Verdì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)
Number of pages10
StatePublished - 2006
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: Jan 22 2006Jan 24 2006


OtherSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityMiami, FL

ASJC Scopus subject areas

  • Software
  • General Mathematics


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

Cite this