University of Versailles
"Enumeration of planar graphs"
A graph is called planar when it can be embedded into the plane so that no two edges cross at an interior point.
How does a planar graph with n vertices look like when n grows to infinity?
Using generating functions and analytic combinatorics, it will be
shown how can one reach results such as:
- give an asymptotic equivalent of the number of planar graphs;
- the number of edges of a planar graph satisfies a central limit
theorem with linear mean and variance;
- the number of connected components of an planar graph is
asymptotically Poisson distributed.
- O. Gimenez and M. Noy, Asymptotic enumeration and limit laws of planar graphs, Journal AMS, vol.22, n.2, 309-329 (2009).
- E.A. Bender, Z. Gao, N.C. Wormald, The number of 2-connected labeled planar graphs, Elec. J. Combin. 9, R43, (2002).
- P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge
Univ. Press (2008).