Finding one tight cycle ^*

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