Generating irreducible triangulations of surfaces

Abstract

Starting with the irreducible triangulations of a fixed surface and splitting vertices, all the triangulations of the surface up to a given number of vertices can be generated. The irreducible triangulations have previously been determined for the surfaces S_0, S_1, N_1,and N_2. An algorithm is presented for generating the irreducible triangulations of a fixed surface using triangulations of other surfaces. This algorithm has been implemented as a computer program which terminates for S_1, S_2, N_1, N_2, N_3, and N_4. Thus the complete sets irreducible triangulations are now also known for S_2, N_3, and N_4, with respective cardinalities 396784, 9708, and 6297982.

11 pages

References in corpus (2)

• Triangulated Manifolds with Few Vertices: Combinatorial Manifolds
• Irreducible triangulations of low genus surfaces

Cited by in corpus (9)

• Surface realization with the intersection edge functional
• Subgraph densities in a surface
• The maximum number of cliques in a graph embedded in a surface
• Optimal packings of congruent circles on a square flat torus
• Isomorphism-free lexicographic enumeration of triangulated surfaces and 3-manifolds
• A fast algorithm for computing irreducible triangulations of closed surfaces in $E^d$
• Some Triangulated Surfaces without Balanced Splitting
• On irreducible triangulations of punctured and pinched surfaces
• Generating families of surface triangulations. The case of punctured surfaces with inner degree at least 4