Finding one tight cycle *

Sergio Cabello, Matt DeVos, Jeff Erickson, Bojan Mohar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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, simple cycle on a given orientable combinatorial surface in 0(n log n) time. The only method previously known for this problem was to compute the globally shortest non-contractible or non-separating cycle in O(min{g 3, 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 0(n log n) time and a tight octagonal decomposition in O(gn log n) time.

Original languageEnglish (US)
Title of host publicationProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages527-531
Number of pages5
StatePublished - Dec 1 2008
Event19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States
Duration: Jan 20 2008Jan 22 2008

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other19th Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CitySan Francisco, CA
Period1/20/081/22/08

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Finding one tight cycle <sup>*</sup>'. Together they form a unique fingerprint.

Cite this