Splitting (complicated) surfaces is hard

Erin W. Chambers, Éric Colin De Verdière, Jeff Erickson, Francis Lazarus, Kim Whittlesey

Research output: Contribution to journalArticlepeer-review


Let M be an orientable combinatorial surface. A cycle on M is splitting if it has no self-intersections and it partitions M 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 g and the number of boundary components b of the surface. Specifically, we describe an algorithm to compute the shortest splitting cycle in ( g+b)O(g+b)nlogn time, where n is the complexity of the combinatorial surface.

Original languageEnglish (US)
Pages (from-to)94-110
Number of pages17
JournalComputational Geometry: Theory and Applications
Issue number1-2
StatePublished - Oct 2008


  • Combinatorial surfaces
  • Computational topology
  • Homotopy

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Splitting (complicated) surfaces is hard'. Together they form a unique fingerprint.

Cite this