Finding one tight cycle
Sergio Cabello, Matt DeVos, Jeff Erickson, Bojan Mohar · ACM Transactions on Algorithms · 2010
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{ 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 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 log 2 n ) time.