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: 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 - 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 -