The triangulations of a surface can be generated by repeated splitting of vertices starting with the irreducible triangulations of the surface.

Algorithms for generating triangulations and for generating irreducible triangulations are described in "Generating irreducible triangulations of surfaces".

Some properties of the irreducible triangulations of S₂, N₃, and N₄ are in "Irreducible triangulations of low genus surfaces".

surftri is a computer program which generates triangulations of surfaces.  It is based extensively on the program plantri.  The source for surftri  can be downloaded.  Counts of triangulations are also available.

The surftri download above also contains the lists of the irreducible triangulations of S₀, S₁, N₁, and N₂.  The lists of the irreducible triangulations of S₂, N₃, and N₄. are larger and can be downloaded separately.  Irreducible triangulations with up to 11 or 12 vertices are also available for other surfaces.

Generating Maps on Surfaces

A map is a simple graph embedded in a surface such that every face is simply connected.  Maps can be obtained from triangulations by removing edges.

Algorithms for generating maps are described in the preprint "Generating maps on surfaces".  This generation process uses irreducible maps as described in that paper.  surftri has been modified to generate maps.