Fachbereich Mathematik

Abst rac t We investigate the computational problems associated with combinatorial surfaces. Specifically, we present an algorithm (based on the Brahana-Dehn-Heegaazd p-proach) 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 con-structing canonical generators of the fundamental group of a surface of genus g. This is useful in constructing homeomorphisms between combinatorial surfaces. 1 I n t roduct ion The principal problem in the topology of closed surfaces is the search for the topological invariants of closed sur-faces so that we can tell if two arbitrarily given dosed surfaces are or are not homeomorphic, see e.g. [2]. It fol-lows then, that the principal computational problem is finding efficient methods to compute these invariants and for two closed homeomorphic surfaces, to cotutruct ho-meomorphism. ~ between them. In this paper we present such algorithms. We assume the reader has some faml-liarity with the topology of surfaces (see e.g., [2, 4]). It is well-known that a closed surface can be repre-sented as a simple polygon whose edges are labeled by symbols, each symbol occurring exactly twice, and each symbol being given a sign (:t=). The surface is obtaine