Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

Asymptotic enumeration and limit laws of planar graphs


Authors: Omer Giménez and Marc Noy
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
Published electronically: October 17, 2008
MathSciNet review: 2476775
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. E. A. Bender, Z. Gao, N. C. Wormald, The number of 2-connected labelled planar graphs, Electron. J. Combin. 9 (2002), R43. MR 1946145 (2003i:05071)
  • 2. M. Bodirsky, O. Giménez, M. Kang, M. Noy, Asymptotic enumeration and limit laws of series-parallel graphs, Europ. J. Combin. 28 (2007), 2091-2105. MR 2351512
  • 3. N. Bonichon, C. Gavoille, N. Hanusse, D. Poulalhon, G. Schaeffer, Planar Graphs, via Well-Orderly Maps and Trees, Graphs Combin. 22 (2006), 185-202. MR 2231990 (2007g:05085)
  • 4. A. Denise, M. Vasconcellos, D. J. A. Welsh, The random planar graph, Congr. Numer. 113 (1996), 61-79. MR 1393702 (97e:05171)
  • 5. P. Flajolet, A. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (1990), 216-240. MR 1039294 (90m:05012)
  • 6. P. Flajolet and R. Sedgewick, Analytic combinatorics, to be published in 2008 by Cambridge University Press, preliminary version available at http://algo.inria.fr/flajolet/ Publications.
  • 7. E. Fusy, Quadratic exact-size and linear approximate-size random sampling of planar graphs, Discrete Math. Theor. Comput. Sci. Proc. AD (2005), 125-138. MR 2193112
  • 8. S. Gerke, C. McDiarmid, On the Number of Edges in Random Planar Graphs, Combin. Probab. Comput. 13 (2004), 165-183. MR 2047234 (2005b:05201)
  • 9. S. Gerke, C. McDiarmid, A. Steger, A. Weissl, Random planar graphs with given average degrees, in Combinatorics, Complexity, and Chance. A Tribute to Dominic Welsh, pp. 83-102, Oxford U. Press, Oxford (2007). MR 2314563 (2008b:05161)
  • 10. O. Giménez, M. Noy, Estimating the growth constant of labelled planar graphs, in Mathematics and Computer Science III: Algorithms, Trees, Combinatorics and Probabilities (M. Drmota, P. Flajolet, D. Gardy, B. Gittenberger, eds.), Birkhäuser, Basel, 2004, pp. 133-139. MR 2090501 (2005f:05077)
  • 11. F. Harary, E. Palmer, Graphical Enumeration, Academic Press, New York-London, 1973. MR 0357214 (50:9682)
  • 12. C. McDiarmid, A. Steger, D. Welsh, Random Planar Graphs, J. Combin. Theory Ser. B 93 (2005), 187-205. MR 2117936 (2005k:05221)
  • 13. R. C. Mullin, P. J. Schellenberg, The enumeration of $ c$-nets via quadrangulations, J. Combin. Theory 4 (1968), 259-276. MR 0218275 (36:1362)
  • 14. D. Osthus, H. J. Prömel, A. Taraz, On random planar graphs, the number of planar graphs and their triangulations, J. Combin. Theory Ser. B 88 (2003), 119-134. MR 1973264 (2004a:05068)
  • 15. B. A. Trakhtenbrot, Towards a theory of non-repeating contact schemes, Trudi Mat. Inst. Akad. Nauk SSSR 51 (1958), 226-269 (in Russian). MR 0107474 (21:6199)
  • 16. G. Turán, On the succinct representation of graphs, Discrete Appl. Math. 8 (1984), 289-294. MR 0749658 (85i:05100)
  • 17. W. T. Tutte, A census of planar triangulations, Canad. J. Math. 14 (1962), 21-38. MR 0130841 (24:A695)
  • 18. W. T. Tutte, A census of planar maps, Canad. J. Math. 15 (1963), 249-271. MR 0146823 (26:4343)
  • 19. W. T. Tutte, Connectivity in graphs, University of Toronto Press, Toronto, 1966. MR 0210617 (35:1503)
  • 20. T. R. S. Walsh, Counting labelled three-connected and homeomorphically irreducible two-connected graphs, J. Combin. Theory Ser. B 32 (1982), 1-11. MR 0649833 (83k:05058a)
  • 21. H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932), 150-168. MR 1506881

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 05A16, 05C30, 05C10

Retrieve articles in all journals with MSC (2000): 05A16, 05C30, 05C10


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

DOI: https://doi.org/10.1090/S0894-0347-08-00624-3
Keywords: Planar graph, random planar graph, asymptotic enumeration, limit law, normal law, analytic combinatorics.
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.
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society