We consider the problem of cutting a set of edges on a polyhedral
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 nO(g+k),
where n is the combinatorial complexity, g is the
genus, and k is the number of boundary components of the
input surface. Finally, we describe a greedy algorithm that outputs
a O( log2 g)-approximation of the minimum cut
graph in O(g2 n log n) time.
@string{DCG = "Discrete Comput. Geom."}
@article{eh-ocsid-04,
author = "J. Erickson and S. {Har-Peled}",
title = "Optimally Cutting a Surface into a Disk",
journal = DCG,
volume = 31,
number = 1,
pages = {37--59},
year = 2004
}