Computational complexity of combinatorial surfaces
Gert Vegter, Chee Keng Yap · 1990
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 Ο(n log n) time, where n is the total number of vertices, edges and faces. We also give an Ο(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.