## Asymptotic enumeration and limit laws of planar graphs

HTML articles powered by AMS MathViewer

- by Omer Giménez and Marc Noy PDF
- J. Amer. Math. Soc.
**22**(2009), 309-329 Request permission

## 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.## References

- Edward A. Bender, Zhicheng Gao, and Nicholas C. Wormald,
*The number of labeled 2-connected planar graphs*, Electron. J. Combin.**9**(2002), no. 1, Research Paper 43, 13. MR**1946145** - Manuel Bodirsky, Omer Giménez, Mihyun Kang, and Marc Noy,
*Enumeration and limit laws for series-parallel graphs*, European J. Combin.**28**(2007), no. 8, 2091–2105. MR**2351512**, DOI 10.1016/j.ejc.2007.04.011 - Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon, and Gilles Schaeffer,
*Planar graphs, via well-orderly maps and trees*, Graphs Combin.**22**(2006), no. 2, 185–202. MR**2231990**, DOI 10.1007/s00373-006-0647-2 - Alain Denise, Marcio Vasconcellos, and Dominic J. A. Welsh,
*The random planar graph*, Congr. Numer.**113**(1996), 61–79. Festschrift for C. St. J. A. Nash-Williams. MR**1393702** - Philippe Flajolet and Andrew Odlyzko,
*Singularity analysis of generating functions*, SIAM J. Discrete Math.**3**(1990), no. 2, 216–240. MR**1039294**, DOI 10.1137/0403019
FS P. Flajolet and R. Sedgewick, - Éric Fusy,
*Quadratic exact-size and linear approximate-size random generation of planar graphs*, 2005 International Conference on Analysis of Algorithms, Discrete Math. Theor. Comput. Sci. Proc., AD, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2005, pp. 125–138. MR**2193112** - Stefanie Gerke and Colin McDiarmid,
*On the number of edges in random planar graphs*, Combin. Probab. Comput.**13**(2004), no. 2, 165–183. MR**2047234**, DOI 10.1017/S0963548303005947 - Stefanie Gerke, Colin McDiarmid, Angelika Steger, and Andreas Weißl,
*Random planar graphs with given average degree*, Combinatorics, complexity, and chance, Oxford Lecture Ser. Math. Appl., vol. 34, Oxford Univ. Press, Oxford, 2007, pp. 83–102. MR**2314563**, DOI 10.1093/acprof:oso/9780198571278.003.0006 - Omer Giménez and Marc Noy,
*Estimating the growth constant of labelled planar graphs*, Mathematics and computer science. III, Trends Math., Birkhäuser, Basel, 2004, pp. 133–139. MR**2090501** - Frank Harary and Edgar M. Palmer,
*Graphical enumeration*, Academic Press, New York-London, 1973. MR**0357214** - Colin McDiarmid, Angelika Steger, and Dominic J. A. Welsh,
*Random planar graphs*, J. Combin. Theory Ser. B**93**(2005), no. 2, 187–205. MR**2117936**, DOI 10.1016/j.jctb.2004.09.007 - R. C. Mullin and P. J. Schellenberg,
*The enumeration of $c$-nets via quadrangulations*, J. Combinatorial Theory**4**(1968), 259–276. MR**218275**, DOI 10.1016/S0021-9800(68)80007-9 - Deryk Osthus, Hans Jürgen Prömel, and Anusch Taraz,
*On random planar graphs, the number of planar graphs and their triangulations*, J. Combin. Theory Ser. B**88**(2003), no. 1, 119–134. MR**1973264**, DOI 10.1016/S0095-8956(02)00040-0 - B. A. Trahtenbrot,
*The theory of non-repeating contact schemes*, Trudy Mat. Inst. Steklov.**51**(1958), 226–269 (Russian). MR**0107474** - György Turán,
*On the succinct representation of graphs*, Discrete Appl. Math.**8**(1984), no. 3, 289–294. MR**749658**, DOI 10.1016/0166-218X(84)90126-4 - W. T. Tutte,
*A census of planar triangulations*, Canadian J. Math.**14**(1962), 21–38. MR**130841**, DOI 10.4153/CJM-1962-002-9 - W. T. Tutte,
*A census of planar maps*, Canadian J. Math.**15**(1963), 249–271. MR**146823**, DOI 10.4153/CJM-1963-029-x - W. T. Tutte,
*Connectivity in graphs*, Mathematical Expositions, No. 15, University of Toronto Press, Toronto, Ont.; Oxford University Press, London, 1966. MR**0210617**, DOI 10.3138/9781487584863 - T. R. S. Walsh,
*Counting labelled three-connected and homeomorphically irreducible two-connected graphs*, J. Combin. Theory Ser. B**32**(1982), no. 1, 1–11. MR**649833**, DOI 10.1016/0097-3165(82)90061-9 - Hassler Whitney,
*Congruent Graphs and the Connectivity of Graphs*, Amer. J. Math.**54**(1932), no. 1, 150–168. MR**1506881**, DOI 10.2307/2371086

*Analytic combinatorics*, to be published in 2008 by Cambridge University Press, preliminary version available at http://algo.inria.fr/flajolet/Publications.

## Additional Information

**Omer Giménez**- Affiliation: Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Jordi Girona 1–3, 08034 Barcelona, Spain
- Email: Omer.Gimenez@upc.edu
**Marc Noy**- Affiliation: Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Jordi Girona 1–3, 08034 Barcelona, Spain
- Email: Marc.Noy@upc.edu
- Received by editor(s): August 3, 2005
- Published electronically: October 17, 2008
- Additional Notes: The first author’s research was supported in part by Project MTM2005-08618C02-01.
- © Copyright 2008
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: J. Amer. Math. Soc.
**22**(2009), 309-329 - MSC (2000): Primary 05A16, 05C30; Secondary 05C10
- DOI: https://doi.org/10.1090/S0894-0347-08-00624-3
- MathSciNet review: 2476775