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 graphsArticle

Authors: 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

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)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: Random graph,planar graph,diameter,bivariate generating functions,singularity analysis,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]
Funding:
    Source : OpenAIRE Graph
  • Combinatorial methods, from enumerative topology to random discrete structures and compact data representations.; Funder: European Commission; Code: 208471

3 Documents citing this article

Consultation statistics

This page has been seen 180 times.
This article's PDF has been downloaded 182 times.