# On the diameter of random planar graphs

Abstract : 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.
Keywords :
Type de document :
Communication dans un congrès
Drmota, Michael and Gittenberger, Bernhard. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pp.65-78, 2010, DMTCS Proceedings
Domaine :

Littérature citée [19 références]

https://hal.inria.fr/hal-00714713
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 16:33:24
Dernière modification le : jeudi 11 janvier 2018 - 06:19:44
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:10:18

### Fichier

dmAM0105.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-00714713, version 2

### Citation

Guillaume Chapuy, Eric Fusy, Omer Gimenez, Marc Noy. On the diameter of random planar graphs. Drmota, Michael and Gittenberger, Bernhard. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pp.65-78, 2010, DMTCS Proceedings. 〈hal-00714713v2〉

### Métriques

Consultations de la notice

## 218

Téléchargements de fichiers