Geodesic
On the diameter of random planar graphs
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (2010).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2010_special_258_a26,
     author = {Chapuy, Guillaume and Fusy, Eric and Gimenez, Omer and Noy, Marc},
     title = {On the diameter of random planar graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)},
     year = {2010},
     doi = {10.46298/dmtcs.2790},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2790/}
}
TY  - JOUR
AU  - Chapuy, Guillaume
AU  - Fusy, Eric
AU  - Gimenez, Omer
AU  - Noy, Marc
TI  - On the diameter of random planar graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2010
VL  - DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2790/
DO  - 10.46298/dmtcs.2790
LA  - en
ID  - DMTCS_2010_special_258_a26
ER  - 
%0 Journal Article
%A Chapuy, Guillaume
%A Fusy, Eric
%A Gimenez, Omer
%A Noy, Marc
%T On the diameter of random planar graphs
%J Discrete mathematics & theoretical computer science
%D 2010
%V DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2790/
%R 10.46298/dmtcs.2790
%G en
%F DMTCS_2010_special_258_a26
Chapuy, Guillaume; Fusy, Eric; Gimenez, Omer; Noy, Marc. On the diameter of random planar graphs. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (2010). doi : 10.46298/dmtcs.2790. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2790/

Cité par Sources :