Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
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
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?)


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: http://dx.doi.org/10.1090/S0894-0347-08-00624-3
PII: S 0894-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.