Combinatorial methods, from enumerative topology to random discrete structures and compact data representations.
Indicators
612
Views
604
Downloads
On the diameter of random planar graphs
Guillaume Chapuy (1), Eric Fusy (2), Omer Gimenez (3), Marc Noy (4)
(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
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
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
