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 Σ issplittingif 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 ing^{O(g)}n^{2}logntime.

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