Asymptotic enumeration and limit laws of planar graphs

Giménez, Omer¹ ; Noy, Marc²

¹ Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Jordi Girona 1–3, 08034 Barcelona, Spain
² Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Jordi Girona 1–3, 08034 Barcelona, Spain

Journal of the American Mathematical Society, Tome 22 (2009) no. 2, pp. 309-329

Résumé

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.

Détail

DOI : 10.1090/S0894-0347-08-00624-3

Bibliographie

[1] Bender, Edward A., Gao, Zhicheng, Wormald, Nicholas C. The number of labeled 2-connected planar graphs Electron. J. Combin. 2002

[2] Bodirsky, Manuel, Gimã©Nez, Omer, Kang, Mihyun, Noy, Marc Enumeration and limit laws for series-parallel graphs European J. Combin. 2007 2091 2105

[3] Bonichon, Nicolas, Gavoille, Cyril, Hanusse, Nicolas, Poulalhon, Dominique, Schaeffer, Gilles Planar graphs, via well-orderly maps and trees Graphs Combin. 2006 185 202

[4] Denise, Alain, Vasconcellos, Marcio, Welsh, Dominic J. A. The random planar graph Congr. Numer. 1996 61 79

[5] Flajolet, Philippe, Odlyzko, Andrew Singularity analysis of generating functions SIAM J. Discrete Math. 1990 216 240

[6] Fusy, ÉRic Quadratic exact-size and linear approximate-size random generation of planar graphs 2005 125 138

[7] Gerke, Stefanie, Mcdiarmid, Colin On the number of edges in random planar graphs Combin. Probab. Comput. 2004 165 183

[8] Gerke, Stefanie, Mcdiarmid, Colin, Steger, Angelika, WeiãŸL, Andreas Random planar graphs with given average degree 2007 83 102

[9] Gimã©Nez, Omer, Noy, Marc Estimating the growth constant of labelled planar graphs 2004 133 139

[10] Harary, Frank, Palmer, Edgar M. Graphical enumeration 1973

[11] Mcdiarmid, Colin, Steger, Angelika, Welsh, Dominic J. A. Random planar graphs J. Combin. Theory Ser. B 2005 187 205

[12] Mullin, R. C., Schellenberg, P. J. The enumeration of 𝑐-nets via quadrangulations J. Combinatorial Theory 1968 259 276

[13] Osthus, Deryk, Prã¶Mel, Hans Jã¼Rgen, Taraz, Anusch On random planar graphs, the number of planar graphs and their triangulations J. Combin. Theory Ser. B 2003 119 134

[14] Trahtenbrot, B. A. The theory of non-repeating contact schemes Trudy Mat. Inst. Steklov. 1958 226 269

[15] Turã¡N, Gyã¶Rgy On the succinct representation of graphs Discrete Appl. Math. 1984 289 294

[16] Tutte, W. T. A census of planar triangulations Canadian J. Math. 1962 21 38

[17] Tutte, W. T. A census of planar maps Canadian J. Math. 1963 249 271

[18] Tutte, W. T. Connectivity in graphs 1966

[19] Walsh, T. R. S. Counting labelled three-connected and homeomorphically irreducible two-connected graphs J. Combin. Theory Ser. B 1982 1 11

[20] Whitney, Hassler Congruent Graphs and the Connectivity of Graphs Amer. J. Math. 1932 150 168