On the diameter of random planar graphs

MaRDI QIDQ2959896zbMATH OpenFDO

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

Publication date 10 February 2017

Full work available at URL https://arxiv.org/abs/1203.3079, http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAM0105

zbMATH Keywords

bivariate generating functionsdiameterplanar graphrandom graphsingularity analysis

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We show that the diameter D(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 the probability that D(G_n) lies in the interval (n^{1/4-epsilon},n^{1/4+epsilon}) is greater than 1-exp(-n^{cepsilon}) for {epsilon} small enough and n>n_0(epsilon). We prove similar statements for 2-connected and 3-connected planar graphs and maps.

Recommendations

• On the diameter of random planar graphs
• Random planar graphs
• The diameter of a random graph with bounded diameter
• Random planar maps and graphs with minimum degree two and three
• The diameter of sparse random graphs

Cited in

(14)

• On the norms of the random walks on planar graphs
• Random enriched trees with applications to random graphs
• Quenched local convergence of Boltzmann planar maps
• Skyscraper polytopes and realizations of plane triangulations
• On the distance-profile of random rooted plane graphs
• On the diameter of a class of random graphs
• Asymptotics and random sampling for BCI and BCK lambda terms
• Random graphs from a weighted minor-closed class
• A Bound for the Diameter of Random Hyperbolic Graphs
• On the diameter of random planar graphs
• Longest and shortest cycles in random planar graphs
• Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023
• Random cubic planar graphs converge to the Brownian sphere
• Diameter bounds for planar graphs

This page was built for publication: On the diameter of random planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2959896)