Guillaume Chapuy ; Eric Fusy ; Omer Gimenez ; Marc Noy
-
On the diameter of random planar graphs
dmtcs:2790 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2010,
DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
-
https://doi.org/10.46298/dmtcs.2790
On the diameter of random planar graphsArticle
Authors: Guillaume Chapuy 1; Eric Fusy 2; Omer Gimenez 3; Marc Noy 4
We show that the diameter $D(G_n)$ of a random (unembedded) labelled connected planar graph with $n$ vertices is asymptotically almost surely of order $n^{1/4}$, in the sense that there exists a constant $c>0$ such that $P(D(G_n) \in (n^{1/4-\epsilon} ,n^{1/4+\epsilon})) \geq 1-\exp (-n^{c\epsilon})$ for $\epsilon$ small enough and $n$ large enough $(n \geq n_0(\epsilon))$. We prove similar statements for rooted $2$-connected and $3$-connected embedded (maps) and unembedded planar graphs.
Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Combinatorial methods, from enumerative topology to random discrete structures and compact data representations.; Funder: European Commission; Code: 208471
Mihyun Kang;Michael Missethan, 2021, Longest and shortest cycles in random planar graphs, Random Structures and Algorithms, 60, 3, pp. 462-505, 10.1002/rsa.21040, https://doi.org/10.1002/rsa.21040.