Asymptotic enumeration and limit laws of planar graphs

DOI10.1090/S0894-0347-08-00624-3zbMath1206.05019arXivmath/0501269WikidataQ54272922 ScholiaQ54272922MaRDI QIDQ3079198

Omer Giménez, Marc Noy

Publication date: 2 March 2011

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0501269

zbMATH Keywords

asymptotic enumerationnormal lawplanar graphanalytic combinatoricsrandom planar graphlimit law

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Planar graphs; geometric and topological aspects of graph theory (05C10) Asymptotic enumeration (05A16)

Related Items (64)

The Early Evolution of the Random Graph Process in Planar Graphs and Related Classes ⋮ Classes of graphs embeddable in order-dependent surfaces ⋮ Phase transitions in discrete structures ⋮ Counting coloured planar maps: differential equations ⋮ Generating labeled planar graphs uniformly at random ⋮ Enumeration of bipartite non-crossing geometric graphs ⋮ Counting coloured planar maps ⋮ Triangles in random cubic planar graphs ⋮ Characterisation of symmetries of unlabelled triangulations ⋮ Enumeration of cubic multigraphs on orientable surfaces ⋮ On the number of anchored rectangle packings for a planar point set ⋮ On the Number of Anchored Rectangle Packings for a Planar Point Set ⋮ The maximum degree of random planar graphs ⋮ The Braess' paradox for pendent twins ⋮ Asymptotic properties of random unlabelled block-weighted graphs ⋮ Concentration of maximum degree in random planar graphs ⋮ Random graphs from a weighted minor-closed class ⋮ Quasipolynomiality of the Smallest Missing Induced Subgraph ⋮ On the sum of digits of some sequences of integers ⋮ Threshold functions for small subgraphs in simple graphs and multigraphs ⋮ Longest and shortest cycles in random planar graphs ⋮ Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture ⋮ Threshold functions for small subgraphs: an analytic approach ⋮ The evolution of random graphs on surfaces ⋮ Evolution of the giant component in graphs on orientable surfaces ⋮ Enumeration of labeled 4-regular planar graphs ⋮ Limits of random tree-like discrete structures ⋮ Random cubic planar graphs converge to the Brownian sphere ⋮ Cubic graphs and related triangulations on orientable surfaces ⋮ Asymptotic enumeration and limit laws for graphs of fixed genus ⋮ On the Diameter of Random Planar Graphs ⋮ Local convergence of random planar graphs ⋮ The Evolution of Random Graphs on Surfaces ⋮ Enumeration of labelled 4-regular planar graphs. II: Asymptotics ⋮ Subgraphs of 4-regular planar graphs ⋮ Phase transitions in graphs on orientable surfaces ⋮ Enumeration of unlabeled uniform hypergraphs ⋮ Random planar graphs with bounds on the maximum and minimum degrees ⋮ 3-Connected Cores In Random Planar Graphs ⋮ Random Graphs from a Minor-Closed Class ⋮ Enumeration and limit laws for series-parallel graphs ⋮ An Experimental Study on Generating Planar Graphs ⋮ Root bundles and towards exact matter spectra of F-theory MSSMs ⋮ Logical limit laws for minor-closed classes of graphs ⋮ Random cubic planar graphs revisited ⋮ Random planar maps and graphs with minimum degree two and three ⋮ Topological classification of polynomial complex differential equations with all the critical points of centre type ⋮ Degree distribution in random planar graphs ⋮ Growth constants of minor-closed classes of graphs ⋮ Planar graphs, via well-orderly maps and trees ⋮ Vertices of given degree in series-parallel graphs ⋮ Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs ⋮ Random graphs from a block-stable class ⋮ Subcritical Graph Classes Containing All Planar Graphs ⋮ The enumeration of planar graphs via Wick's theorem ⋮ ExtremalC₄-Free/C₅-Free Planar Graphs ⋮ On the expected number of perfect matchings in cubic planar graphs ⋮ Two critical periods in the evolution of random planar graphs ⋮ Graph classes with given 3-connected components: Asymptotic enumeration and random graphs ⋮ A Census of Plane Graphs with Polyline Edges ⋮ Enumeration of chordal planar graphs and maps ⋮ Unnamed Item ⋮ Geometric biplane graphs. I: Maximal graphs ⋮ Spanning trees in random series-parallel graphs

Cites Work

• On the succinct representation of graphs
• Counting unlabelled three-connected and homeomorphically irreducible two- connected graphs
• On random planar graphs, the number of planar graphs and their triangulations
• Random planar graphs
• The number of labeled 2-connected planar graphs
• Enumeration and limit laws for series-parallel graphs
• Planar graphs, via well-orderly maps and trees
• A Census of Planar Triangulations
• Singularity Analysis of Generating Functions
• Congruent Graphs and the Connectivity of Graphs
• On the Number of Edges in Random Planar Graphs
• The enumeration of c-nets via quadrangulations
• A Census of Planar Maps
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Asymptotic enumeration and limit laws of planar graphs