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, 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 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 (g2n log n) time.
Original language | English (US) |
---|---|
Pages (from-to) | 37-59 |
Number of pages | 23 |
Journal | Discrete and Computational Geometry |
Volume | 31 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2004 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics