Splitting (complicated) surfaces is hard

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Let M be an orientable combinatorial surface without boundary. 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. Specifically, we describe an algorithm to compute the shortest splitting cycle in g O(g)n log n time.

Original languageEnglish (US)
Title of host publicationProceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
PublisherAssociation for Computing Machinery
Number of pages9
ISBN (Print)1595933409, 9781595933409
StatePublished - 2006
Event22nd Annual Symposium on Computational Geometry 2006, SCG'06 - Sedona, AZ, United States
Duration: Jun 5 2006Jun 7 2006

Publication series

NameProceedings of the Annual Symposium on Computational Geometry


Other22nd Annual Symposium on Computational Geometry 2006, SCG'06
Country/TerritoryUnited States
CitySedona, AZ


  • Combinatorial surface
  • Computational topology
  • Splitting cycle
  • Topological graph theory

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


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

Cite this