Splitting (complicated) surfaces is hard

Computational Geometry: Theory and Applications 41(1–2):94–110, 2008.
(Special issue of invited papers from the 22nd European Workshop on Computational Geometry)

Proceedings of the 22nd Annual ACM Symposium on Computational Geometry, 421-429, 2006.

Extended abstract in Proceedings of the 22nd Annual European Workshop on Computational Geometry, 95-98, 2006.

• Download journal version (final except for copy-editing):
• Download SOCG version:
• Download EWCG abstract:

Abstract:

Let Σ be an orientable surface without boundary. A cycle on Σ is splitting if it has no self-intersections and it partitions Σ into two components, neither 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.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 12 Feb 2006