TY - JOUR

T1 - Finding one tight cycle

AU - Cabello, Sergio

AU - Devos, Matt

AU - Erickson, Jeff

AU - Mohar, Bojan

N1 - Copyright:
Copyright 2019 Elsevier B.V., All rights reserved.

PY - 2010/8

Y1 - 2010/8

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

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

KW - Combinatorial surface

KW - Noncontractible cycle

KW - Nonseparating cycle

KW - Topological graph theory

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

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

U2 - 10.1145/1824777.1824781

DO - 10.1145/1824777.1824781

M3 - Article

AN - SCOPUS:77954917057

SN - 1549-6325

VL - 6

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 4

M1 - 61

ER -