## 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms |

Pages | 527-531 |

Number of pages | 5 |

State | Published - 2008 |

Event | 19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States Duration: Jan 20 2008 → Jan 22 2008 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 19th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country/Territory | United States |

City | San Francisco, CA |

Period | 1/20/08 → 1/22/08 |

## ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint

Dive into the research topics of 'Finding one tight cycle^{*}'. Together they form a unique fingerprint.