TY - GEN
T1 - Splitting (complicated) surfaces is hard
AU - Chambers, Erin W.
AU - De Verdière, Éric Colin
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 - 2006
Y1 - 2006
N2 - Let M be an orientable combinatorial surface without boundary. 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. Specifically, we describe an algorithm to compute the shortest splitting cycle in g O(g)n log n time.
AB - Let M be an orientable combinatorial surface without boundary. 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. Specifically, we describe an algorithm to compute the shortest splitting cycle in g O(g)n log n time.
KW - Combinatorial surface
KW - Computational topology
KW - Splitting cycle
KW - Topological graph theory
UR - http://www.scopus.com/inward/record.url?scp=33748180602&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33748180602&partnerID=8YFLogxK
U2 - 10.1145/1137856.1137918
DO - 10.1145/1137856.1137918
M3 - Conference contribution
AN - SCOPUS:33748180602
SN - 1595933409
SN - 9781595933409
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 421
EP - 429
BT - Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
PB - Association for Computing Machinery
T2 - 22nd Annual Symposium on Computational Geometry 2006, SCG'06
Y2 - 5 June 2006 through 7 June 2006
ER -