Optimally cutting a surface into a disk
<|reference_start|>Optimally cutting a surface into a disk: 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 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.<|reference_end|>
@article{erickson2002optimally,
    title={Optimally cutting a surface into a disk},
    author={Jeff Erickson and Sariel Har-Peled},
    journal={arXiv preprint arXiv:cs/0207004},
    year={2002},
    archivePrefix={arXiv},
    eprint={cs/0207004},
    primaryClass={cs.CG cs.DS cs.GR}
}