On the diameter of random planar graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2010

On the diameter of random planar graphs

Résumé

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.
Fichier principal
Vignette du fichier
dmAM0105.pdf (345.76 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-00714713 , version 1 (05-07-2012)
hal-00714713 , version 2 (20-08-2015)

Identifiants

Citer

Guillaume Chapuy, Eric Fusy, Omer Gimenez, Marc Noy. On the diameter of random planar graphs. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.65-78, ⟨10.46298/dmtcs.2790⟩. ⟨hal-00714713v2⟩
533 Consultations
695 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More