Skip to Main content Skip to Navigation
Conference papers

Splitting (Complicated) Surfaces is Hard

Abstract : 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.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00080564
Contributor : Francis Lazarus Connect in order to contact the contributor
Submitted on : Monday, June 19, 2006 - 4:37:01 PM
Last modification on : Thursday, March 17, 2022 - 10:08:26 AM
Long-term archiving on: : Monday, April 5, 2010 - 11:03:18 PM

Identifiers

  • HAL Id : hal-00080564, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

155

Files downloads

204