On the Diameter of Random Planar Graphs

DOI10.1017/S0963548314000467zbMath1371.05258OpenAlexW3105999784MaRDI QIDQ5364218

Guillaume Chapuy, Omer Giménez, Marc Noy, Éric Fusy

Publication date: 4 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548314000467

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) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Connectivity (05C40)

Related Items

Concentration of maximum degree in random planar graphs ⋮ The evolution of random graphs on surfaces ⋮ A phase transition in block-weighted random maps ⋮ Random cubic planar graphs converge to the Brownian sphere ⋮ Local convergence of random planar graphs ⋮ The Evolution of Random Graphs on Surfaces ⋮ Random graphs from a block-stable class ⋮ Fast and compact planar embeddings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Uniqueness and universality of the Brownian map
• The Brownian map is the scaling limit of uniform random plane quadrangulations
• Census of planar maps: From the one-matrix model solution to a combinatorial proof
• Limit of normalized quadrangulations: the Brownian map
• Scaling limits of bipartite planar maps are homeomorphic to the 2-sphere
• On the sphericity of scaling limits of random planar quadrangulations
• Some families of increasing planar maps
• Une relation fonctionnelle nouvelle sur les cartes planaires pointées
• Counting unlabelled three-connected and homeomorphically irreducible two- connected graphs
• Geodesic distance in planar graphs
• Random planar lattices and integrated superBrownian excursion
• The asymptotic number of rooted maps on a surface. II: Enumeration by vertices and faces
• The number of labeled 2-connected planar graphs
• The topological structure of scaling limits of large planar maps
• Invariance principles for random bipartite planar maps
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• Graph classes with given 3-connected components: Asymptotic enumeration and random graphs
• Trees and spatial topology change in CDT
• The maximum degree of random planar graphs
• Maximal biconnected subgraphs of random planar graphs
• Planar Maps are Well Labeled Trees
• Asymptotic enumeration and limit laws of planar graphs
• A Bijection for Rooted Maps on Orientable Surfaces
• The Size of the Largest Components in Random Planar Maps
• The Distribution of Heights of Binary Trees and Other Simple Trees
• The Maximum Degree of Series-Parallel Graphs
• A Census of Planar Maps