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