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: [email protected] (E.W. Chambers), [email protected] (É. Colin de Verdière), [email protected] (J. Erickson), [email protected] (F. Lazarus), [email protected] (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
SN - 0925-7721
VL - 41
SP - 94
EP - 110
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 1-2
ER -