We investigate the computational problems associated with combinatorial surfaces. Specifically, we present an algorithm (based on the Brahana-Dehn-Heegaazd 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. 1 The principal problem in the topology of closed surfaces is the search for the topological invariants of closed surfaces so that we can tell if two arbitrarily given dosed surfaces are or are not homeomorphic, see e.g. [2]. It follows then, that the principal computational problem is finding efficient methods to compute these invariants and for two closed homeomorphic surfaces, to cotutruct homeomorphism.~ between them. In this paper we present such algorithms. We assume the reader has some famlliarity with the topology of surfaces (see e.g., [2, 4] ). It is well-known that a closed surface can be represented 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 obtained * Supported by the ESPRIT II Basic Research Action of the E.C. under contract No.3075 (Project ALCOM). tOn leave from the Courartt ].n.stltute, New York University. This author is also supported by the German Science Foundatlon (DFG) and NSF Grants #DCR-84-01898 and ~CCR-87-03458. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. by identifying the pair of edges corresponding to a symbol, where the signs indicate whether the identification is with (equal signs) or without (opposite signs) a twist. See Figure 1 for an octogonal schema corresponding to the double-torus. Conversely, any simple polygon in which each edge is labeled by an arbitrarily signed symbol and each unsigned symbol appears exactly twice represents a closed surface. We call this a polygonal achema of the surface. Furthermore, each homeomorphic class of surface has a canonical form in the polygonal schema. There is a classic algorithm for converting a polygonal schema into its canonical form. The algorithm is essentially due to Brahana (see [1] ), although the classification theorem is from Dehn and Heegaard. We call it the Brahana-DelmHeegaard (alphabetical order) or BDH algorithm. It is not obvious how this algorithm can be implemented in o(n 2) time, where n is the total number of vertices, edges and faces. We will present an algorithm that runs in time O(nlog n). Our second result shows that, given a triangulated closed surface, we can construct a 'canonical' set of generators for its fundamental group in time O(nlogn + gn), where g is the genus of the surface. Using this, we can cut open the surface into a planar polygon such that its boundary must be identified in a certain canonical way. 102
Vegter and Yap REF showed that canonical schemata exist with total complexity O(ng) where g is the surface genus; this bound is tight in the worst case, and they also showed that a canonical schema can be found in time O(ng).
Computational complexity of combinatorial surfaces
SCG '90
Mathematics Computer Science