Séminaire du 22 novembre 04, by Omer Gimenez.

Asymptotic enumeration of labelled planar graphs

Bender, Gao and Wormald studied the generating function of labelled 2-connected planar graphs. They proved that the asymptotic number of such graphs on $n$ vertices is $cn^{-7/2}\gamma_b^n$, and they provided an expression for $\gamma_b\simeq 26.18$. On the other hand, it is well known that the generating functions of the connected and the 2-connected planar graphs are related by an easy equation. We use this fact to prove that the asymptotic number of labelled connected planar graphs on $n$ vertices is $dn^{-7/2}\gamma^n$, and to obtain an expression for $\gamma\simeq 27.22687$. We also present several applications.

It is joint work of Omer Gimenez and Marc Noy.

Virginie Collette
Last modified: Mon Sep 20 15:06:18 CEST 2004