Generations of triangulations of the sphere
Rufus Bowen, Stephen Fisk · Mathematics of Computation · 1967
It is easily seen that there is only one triangulation of the sphere with four vertices and one with five. This paper concerns an algorithm for finding all (nonisomorphic) triangulations of the 2-sphere with N vertices from those with N - 1. Triangulation shall always refer to a triangulation of the 2-sphere. First we develop a method for generating all triangulations with N vertices which may yield several triangulations of the same isomorphism type, and then we describe an isomorphism routine for elimninating these duplications. Let T be a triangulation with N _ 5 vertices, E edges, and F faces. Let Xk denote the number of vertices of T of valency k. Then 3F = 2E as each face is a triangle and each edge is on two faces, and 2E =E kXk as each edge is incident to two vertices. Hence 6F - 6E -2E = - kXk and by Euler's fornmula we have