On the Diameter of Random Planar Graphs

2012/03/31 by Guillaume Chapuy, GUILLAUME CHAPUY, ÉRIC FUSY +5
Computer Science · Mathematics · #1-planar graph #Computational Geometry and Mesh Generation #Graph #Limits and Structures in Graph Theory #Outerplanar graph #Planar #Planar graph #Random graph #Stochastic processes and statistical mechanics #math.CO

paper · pdf · doi:10.1017/s0963548314000467

published as Combinator. Probab. Comp. 24 (2015) 145-178 · 24 pages, 7 figures

arxiv created 2014/01/10 · openalex publication_date 2014/09/18 · arxiv updated 2019/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We show that the diameter diam( G n ) of a random labelled connected planar graph with n vertices is equal to n 1/4+o(1) , in probability. More precisely, there exists a constant c > 0 such that P(\D(G_n)∈(n^1/4-\e,n^1/4+\e))≥ 1-exp(-n^c\e) for ε small enough and n ≥ n 0 (ε) . We prove similar statements for 2-connected and 3-connected planar graphs and maps.

Citations

• Asymptotic enumeration and limit laws of planar graphs
• Census of planar maps: from the one-matrix model solution to a combinatorial proof
• The Brownian map is the scaling limit of uniform random plane quadrangulations