Optimally cutting a surface into a disk

Discrete & Computational Geometry 31(1):37-59, 2004.
(Special issue of invited papers from the 18th Annual ACM Symposium on Computational Geometry)

Proceedings of the 18th Annual ACM Symposium on Computational Geometry, 244-253, 2002.

arXiv:cs.CG/0207004

• Download revised journal version (final except for copy editing):
• Official journal version from Springer-Verlag (subscription required)

• Download SoCG version (© 2002 ACM):
• Official SOCG version from ACM's Digital Library (subscription or $5 payment required)

Abstract:

We consider the problem of cutting a subset of edges of a triangulated oriented manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or their total length. We show that this problem is NP-hard, even for manifolds without boundary and for punctured spheres. We also describe an algorithm with running time n^O(g+k), where n is the number of vertices, g is the genus, and k is the number of boundary components of the input surface. Finally, we describe a greedy algorithm that outputs an O(log² g)-approximation of the minimum cut graph in O(g²n log n) time.

Erratum:
The algorithms in Section 5 do not correctly compute the shortest essential cycle in surfaces with boundary, although they do correctly compute the shortest non-contractible cycle in any surface. (A cycle is contractible if it is homotopic to a point; a cycle is inessential homotopic to a point or a boundary cycle.) See “Computing the shortest essential cycle” for an explanation of the error and correct algorithms.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 05 Dec 2009