Lindley Hall 102 (3:45pm-4:15pm)

Erin Chambers
University of Illinois at Urbana-Champaign

Splitting (Complicated) Surfaces is Hard

Let $M$ be an orientable surface without boundary. A cycle on $M$ is splitting if it has no self-intersections and it partitions $M$ 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^2 \log n$ time.

To appear in Proceedings of SoCG 2007: 23rd Annual ACM Symposium on Computational Geometry (Gyeongju, South Korea). Joint work with Eric Colin de Verdiere, Jeff Erickson, Francis Lazarus, and Kim Whittlesey. Full paper here.