Computational complexity of combinatorial surfaces

Gert Vegter, Chee K. Yap

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


We investigate the computational problems associated with combinatorial surfaces. Specifically, we present an algorithm (based on the Brahana-Dehn-Heegaard approach) for transforming the polygonal schema of a closed triangulated surface into its canonical form in O(n log n) time, where n is the total number of vertices, edges and faces. We also give an O(n log n + gn) algorithm for constructing canonical generators of the fundamental group of a surface of genus g. This is useful in constructing homeomorphisms between combinatorial surfaces.

Original languageEnglish (US)
Title of host publicationProc Sixth Annu Symp Comput Geom
PublisherPubl by ACM
Number of pages10
ISBN (Print)0897913620, 9780897913621
StatePublished - 1990
EventProceedings of the Sixth Annual Symposium on Computational Geometry - Berkeley, CA, USA
Duration: Jun 6 1990Jun 8 1990

Publication series

NameProc Sixth Annu Symp Comput Geom


ConferenceProceedings of the Sixth Annual Symposium on Computational Geometry
CityBerkeley, CA, USA

ASJC Scopus subject areas

  • General Engineering

Cite this