Finding one tight cycle

Sergio Cabello, Matt Devos, Jeff Erickson, Bojan Mohar

Research output: Contribution to journalArticle

Abstract

A cycle on a combinatorial surface is tight if it as short as possible in its (free) homotopy class. We describe an algorithm to compute a single tight, noncontractible, essentially simple cycle on a given orientable combinatorial surface in O(n log n) time. The only method previously known for this problem was to compute the globally shortest noncontractible or nonseparating cycle in O(min{g3, n} n log n) time, where g is the genus of the surface. As a consequence, we can compute the shortest cycle freely homotopic to a chosen boundary cycle in O (n log n) time, a tight octagonal decomposition in O(gn log n) time, and a shortest contractible cycle enclosing a nonempty set of faces in O(n log2 n) time.

Original languageEnglish (US)
Article number61
JournalACM Transactions on Algorithms
Volume6
Issue number4
DOIs
StatePublished - Aug 2010

Keywords

  • Combinatorial surface
  • Noncontractible cycle
  • Nonseparating cycle
  • Topological graph theory

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint Dive into the research topics of 'Finding one tight cycle'. Together they form a unique fingerprint.

Cite this