| Abstract: | 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, minimizingeither the total number of cut edges or their total length. We show that thisproblem is NP-hard in general, even for manifolds without boundary and for puncturedspheres. We also describe an algorithm with running time n O(g+k), where n isthe combinatorial complexity, g is the genus, and k is the number of boundarycomponents of the input surface. Finally, we describe a greedy algorithm thatoutputs a O(log2 g)-approximation of the minimum cut graph in O(g 2 n log n)time. |
