Splitting (Complicated) Surfaces is Hard

Erin W. Chambers (1) , Eric Colin de Verdière (2) , Jeff Erickson (1) , Francis Lazarus (3) , Kim Whittlesey (4)

1 Department. of Computer Science [Illinois]
2 LIENS - Laboratoire d'informatique de l'école normale supérieure
3 LIS - Laboratoire des images et des signaux
4 Department of Mathematics

Let $\MM$ be an orientable combinatorial surface without boundary. A cycle on $\MM$ is \emph{splitting} if it has no self-intersections and it partitions $\MM$ into two components, neither of which is 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.

Mots clés: computational topology; topological graph theory; combinatorial surface; splitting cycle

Domaines: Algorithme et structure de données [cs.DS]; Performance et fiabilité [cs.PF]

Erin W. Chambers, Eric Colin de Verdière, Jeff Erickson, Francis Lazarus, Kim Whittlesey. Splitting (Complicated) Surfaces is Hard. ACM Symp. on Computational Geometry (SOCG'06), 2006, France. pp.421-429. ⟨hal-00080564⟩