Abstract
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 language | English (US) |
|---|---|
| Pages (from-to) | 912-930 |
| Number of pages | 19 |
| Journal | Discrete and Computational Geometry |
| Volume | 44 |
| Issue number | 4 |
| DOIs | |
| State | Published - 2010 |
Keywords
- 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