• Nicolas Pouyanne, 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.
Bibliography :
1. O. Gimenez and M. Noy, Asymptotic enumeration and limit laws of planar graphs, Journal AMS, vol.22, n.2, 309-329 (2009).
2. E.A. Bender, Z. Gao, N.C. Wormald, The number of 2-connected labeled planar graphs, Elec. J. Combin. 9, R43, (2002).
3. P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge Univ. Press (2008).