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
NULL##NULL##NULL##NULL
Guillaume Chapuy;Eric Fusy;Omer Gimenez;Marc Noy
1 Department of Mathematics [Burnaby]
2 Laboratoire d'informatique de l'École polytechnique [Palaiseau]
3 Departament Llenguatges i Sistemes Informatics,
4 Departament de Matemàtica Aplicada II
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