Splitting (complicated) surfaces is hard

Written with Erin Chambers*, Éric Colin de Verdière, Francis Lazarus, and Kim Whittlesey.

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.


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 gO(g) n2 log n time.


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