Enumeration of rooted planar triangulations with respect to diagonal flips (Q1818215)

A planar near-triangulation is a embedding in the plane of a 2-connected graph without loops so that all interior faces are triangles; where there are no multiple edges, the near-triangulation is strict. A near-triangulation is of type \([n,m]\) if it has \(n\) interior vertices, and has \(m\) vertices in the boundary of the exterior face; it is rooted if an edge of the exterior face is selected as the root, and oriented; a triangulation has \(m=3\). If \(e\) is an edge having ends \(a\) and \(b\), and is not in the boundary of the exterior face, and if \(abc\) and \(abd\) are the two facial triangles incident with \(e\), the operation of replacing edge \(e\) by edge \(cd\) is a diagonal flip; \(e\) is flippable if flipping it does not create a loop, i.e.\ if \(c\neq d\); in a triangulation, one requires additionally that the flipping does not create multiple edges. From the authors' abstract: We (\dots) enumerate two families of rooted planar near-triangulations (\dots) with respect to the number of flippable edges. It is shown that their generating functions are algebraic. Simple explicit expressions are obtained for the expected number of flippable edges in a random near-triangulation. Asymptotic estimates are obtained for the first two moments, which are then used to show that the numbers of flippable edges in a random near-triangulation and strict near-triangulation are sharply concentrated around \(5n/2\) and \(9n/4\), respectively.