On random planar graphs, the number of planar graphs and their triangulations (Q1405106)

This paper investigates random planar graphs---the number of planar graphs and their triangulations. A random planar graph \(P_n\) is selected uniformly from \(\alpha_n\) where \(\alpha_n\) is the set of labelled planar graphs with \(\{1,2,3,\dots, n\}\) as vertex set. The following are the main results: (1) \(|\alpha_n|\leq n!(37.3)^{n+o(n)}\). (2) Every labelled planar graph \(G\) with \(n\) vertices and \(m\) edges is contained in at least \(3^{(3n- m)/2}E\) labelled triangulations on \(n\) vertices, where \(E\) is an absolute constant. (3) Almost all graphs in \(\alpha_n\) have less than 2.56 edges.