Let P-n be the set of labelled planar graphs with n vertices. Denise, Vasconcellos and Welsh proved that \P-n\ less than or equal to n! (75.8)(n+o(n)) and Bender, Gao and Wormald proved that \P-n\ greater than or equal to n! (26.1)(n+o(n)). Gerke and McDiarmid proved that almost all graphs in P-n have at least 13/7n edges. In this paper, we show that \P-n\ less than or equal to n! (37.3)(n+o(n)) and that almost all graphs in P-n 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 epsilon3((3n-m)/2) labelled triangulations on n vertices, where epsilon 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. (C) 2002 Elsevier Science (USA). All rights reserved.
