Optimally cutting a surface into a disk

We consider the problem of cutting a subset of the edges of 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 in general, 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 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)(log(2) g)-approximation of the minimum cut graph in O(g(2)n log n) time.