On random planar graphs, the number of planar graphs and their triangulations
By Deryk Osthus, Hans Jürgen Prömel, and Anusch TarazJournal of Combinatorial Theory (B), 88: 119-134, 2003
Abstract
Let Pn be the set of labelled planar graphs with n vertices. Denise, Vasconcellos and Welsh proved that |Pn| <= n! 75.8n+o(n) and Bender, Gao and Wormald proved that |Pn| >= n! 26.1n+o(n). McDiarmid proved that almost all graphs in Pn have at least 13/7n edges. In this paper, we show that |Pn| <= n! 37.3n+o(n) and that almost all graphs in Pn have at most 2.56n edges. The proof relies on a result of Tutte on the number of plane triangulations, the above result of Bender, Gao and Wormald and the following result, which we also prove in this paper: every labelled planar graph G with n vertices and m edges is contained in at least e 3(3n-m)/2 labelled triangulations on n vertices, where e is an absolute constant. In other words, the number of triangulations of a planar graph is exponential in the number of edges which are needed to triangulate it. We also show that this bound on the number of triangulations is essentially best possible.
Download
- ps - planar.ps
English