Computing the shortest essential cycle

Jeff Erickson, Pratik Worah

Research output: Contribution to journalArticlepeer-review


An essential cycle on a surface is a simple cycle that cannot be continuously deformed to a point or a single boundary. We describe algorithms to compute the shortest essential cycle in an orientable combinatorial surface in O(n2log n) time, or in O(n log n) time when both the genus and number of boundaries are fixed. Our results correct an error in a paper of Erickson and Har-Peled (Discrete Comput. Geom. 31(1):37-59, 2004).

Original languageEnglish (US)
Pages (from-to)912-930
Number of pages19
JournalDiscrete and Computational Geometry
Issue number4
StatePublished - 2010


  • Combinatorial surface
  • Computational topology
  • Essential cycles
  • Topological graph theory

ASJC Scopus subject areas

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


Dive into the research topics of 'Computing the shortest essential cycle'. Together they form a unique fingerprint.

Cite this