How to generate all triangulations of an orientable surface? $\newcommand{\comb}{\mathrm{comb}}$Consider an orientable surface $S$ with punctures and boundaries (each boundary having at least a marked point).
A triangulation, up to orientation preserving homeomorphisms, of $S$ is described by a collection $T_{\comb}$ of triangles $t$ which themselves are cyclically ordered triples of labels associated to each edge, $t=(e_1,e_2,e_3)$. Let me call these data a combinatorial triangulation.
A combinatorial triangulation $T_{\comb}$ does not label unically a triangulation up to homeomorphism, because one can further permute the edge labels $e_i \to e_{\sigma(i)}$.
What are efficient ways to generate all combinatorial triangulations $T_{\comb}$ up to permutation of the edges? In other words, how to generate one combinatorial triangulation for each triangulation of the surface up to homeomorphism?
One way which I know is to use the Whitehead theorem, which says that any two triangulations are related by a sequence of flips (remove one edge from the triangulation and replace it with the other diagonal in the square thus formed). Then one can start from a triangulation, and sequentially flip all edges and then repeat with the triangulations thus obtained. Are there better options?
Clarification:
The triangulations I consider are such that the edges are at the marked points/punctures. For instance for a disk with 4 marked points on the boundaries we have two triangulations:
Let a=(12), b=(23),c=(34),d=(41),e=(13),f=(24), then the two triangulations are ((a,b,e),(c,d,e)) and ((d,a,f),(b,c,f)).
 A: Regarding enumeration: counting triangulations of surfaces with boundaries of prescribed lengts (number of vertices on each) is one with a long history. In the genus-0 case it dates back to Tutte in the sixties: Tutte, W. (1962). A Census of Planar Triangulations. Canadian Journal of Mathematics, 14, 21-38. See also Krikun, Maxim. Explicit enumeration of triangulations with multiple boundaries. Electron. J. Combin. 14 (2007), 61.
For the higher-genus case you could have a look at Goulden, I. P.; Jackson, D. M. The KP hierarchy, branched covers, and triangulations. Adv. Math. 219 (2008), no. 3, 932--951. Or the more physicist-oriented book by B. Eynard, Counting Surfaces, CRM Aisenstadt Chair lectures. But there are many more works out there.
A: Jus as you describe it, breadth first search in the flip graph will generate all combinatorial triangulations (up to relabelling) in time only a small multiple of the size of the output.
Of course, the size of the output is super-exponential in the (unary) size of the topological data, so this is not as nice as it sounds.  (The upper bound comes a labelling argument: see Ben Burton's "isomorphism signatures".  The lower bound comes by importing a similar lower bound from counting cubic graphs.)
I do not know of a quick way to count the number of triangulations.  I agree that such a thing would be very interesting!
A: Thom Sulanke has a program and a paper about this. Check out https://tsulanke.pages.iu.edu/graphs/surftri/ .
Incidentally, Sulanke's method does not require the triangulations to be stored, so memory is not a limitation. An implementation for the planar case is plantri which we have used to make more than $10^{13}$ triangulations .
