TY - GEN

T1 - Finding one tight cycle *

AU - Cabello, Sergio

AU - DeVos, Matt

AU - Erickson, Jeff

AU - Mohar, Bojan

PY - 2008/12/1

Y1 - 2008/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=58449112507&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58449112507&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:58449112507

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 527

EP - 531

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -