• 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).