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 graphs
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
Quenched Local Convergence of Boltzmann Planar Maps
3 Documents citing this article
Source : OpenCitations
Bodini, O.; Gardy, D.; Jacquot, A., 2013, Asymptotics And Random Sampling For BCI And BCK Lambda Terms, Theoretical Computer Science, 502, pp. 227-238, 10.1016/j.tcs.2013.01.008.
Kang, Mihyun; Missethan, Michael, 2021, Longest And Shortest Cycles In Random Planar Graphs, Random Structures And Algorithms, 60, 3, pp. 462-505, 10.1002/rsa.21040.
Stufler, Benedikt, 2021, Quenched Local Convergence Of Boltzmann Planar Maps, Journal Of Theoretical Probability, 35, 2, pp. 1324-1342, 10.1007/s10959-021-01089-2.