Asymptotic enumeration and limit laws of planar graphs

Abstract:

We present a complete analytic solution to the problem of counting planar graphs. We prove an estimate $g_n \sim g\cdot n^{-7/2} \gamma ^n n!$ for the number $g_n$ of labelled planar graphs on $n$ vertices, where $\gamma$ and $g$ are explicit computable constants. We show that the number of edges in random planar graphs is asymptotically normal with linear mean and variance and, as a consequence, the number of edges is sharply concentrated around its expected value. Moreover we prove an estimate $g(q)\cdot n^{-4}\gamma (q)^n n!$ for the number of planar graphs with $n$ vertices and $\lfloor qn \rfloor$ edges, where $\gamma (q)$ is an analytic function of $q$. We also show that the number of connected components in a random planar graph is distributed asymptotically as a shifted Poisson law $1+P(\nu )$, where $\nu$ is an explicit constant. Additional Gaussian and Poisson limit laws for random planar graphs are derived. The proofs are based on singularity analysis of generating functions and on perturbation of singularities.