TY - JOUR

T1 - Splitting (complicated) surfaces is hard

AU - Chambers, Erin W.

AU - Colin De Verdière, Éric

AU - Erickson, Jeff

AU - Lazarus, Francis

AU - Whittlesey, Kim

N1 - Funding Information:
✩ See http://www.cs.uiuc.edu/~jeffe/pubs/splitting.html for the most recent version of this paper. * Corresponding author. E-mail addresses: erinwolf@uiuc.edu (E.W. Chambers), Eric.Colin.de.Verdiere@ens.fr (É. Colin de Verdière), jeffe@cs.uiuc.edu (J. Erickson), Francis.Lazarus@gipsa-lab.inpg.fr (F. Lazarus), kwhittle@math.uiuc.edu (K. Whittlesey). 1 Research partially supported by an NSF Graduate Research Fellowship and by NSF grant DMS-0528086. 2 Research partially supported by NSF grants CCR-0093348, CCR-0219594, and DMS-0528086.
Funding Information:
Portions of this work were done while all five authors were at the University of Illinois and later at École normale supérieure, thanks to the support of a UIUC/CNRS/INRIA travel grant. We thank the other participants of the 1st UIUC/CNRS/INRIA Workshop on Computational Topology for interesting discussions and meals. We also thank Therese Biedl, Sergio Cabello, Sariel Har-Peled, Martin Kutz, Kevin Milans, and Günter Rote for useful discussions while this work was in progress. We are especially grateful to Martin Kutz for sending us an advance copy of his paper [14].

PY - 2008/10

Y1 - 2008/10

N2 - Let M be an orientable combinatorial surface. A cycle on M is splitting if it has no self-intersections and it partitions M into two components, neither of which is homeomorphic to a disk. In other words, splitting cycles are simple, separating, and non-contractible. We prove that finding the shortest splitting cycle on a combinatorial surface is NP-hard but fixed-parameter tractable with respect to the surface genus g and the number of boundary components b of the surface. Specifically, we describe an algorithm to compute the shortest splitting cycle in ( g+b)O(g+b)nlogn time, where n is the complexity of the combinatorial surface.

AB - Let M be an orientable combinatorial surface. A cycle on M is splitting if it has no self-intersections and it partitions M into two components, neither of which is homeomorphic to a disk. In other words, splitting cycles are simple, separating, and non-contractible. We prove that finding the shortest splitting cycle on a combinatorial surface is NP-hard but fixed-parameter tractable with respect to the surface genus g and the number of boundary components b of the surface. Specifically, we describe an algorithm to compute the shortest splitting cycle in ( g+b)O(g+b)nlogn time, where n is the complexity of the combinatorial surface.

KW - Combinatorial surfaces

KW - Computational topology

KW - Homotopy

UR - http://www.scopus.com/inward/record.url?scp=84867931013&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867931013&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2007.10.010

DO - 10.1016/j.comgeo.2007.10.010

M3 - Article

AN - SCOPUS:84867931013

VL - 41

SP - 94

EP - 110

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

SN - 0925-7721

IS - 1-2

ER -