On the diameter of random planar graphs

Guillaume Chapuy; Éric Fusy; Omer Giménez; Marc Noy

doi:10.1017/S0963548314000467

On the diameter of random planar graphs

Guillaume Chapuy
, Éric Fusy
, Omer Giménez
, Marc Noy

École Polytechnique

Laboratoire d'Informatique (LIX)
Departament de Llenguatges I Sistemes Informàtics
Universidad Politecnica de Catalunia
Dept. de Matemàtica Aplicada II

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

12 Citations (Scopus)

Résumé

We show that the diameter diam(G_n) of a random labelled connected planar graph with n vertices is equal to n^1/4+o(1), in probability. More precisely, there exists a constant c > 0 such that P(diam(G_n) ∈ (n^1/4?∈, n^1/4+∈)) ≥1 ? exp(?n^c∈) for ∈ small enough and n ≥n₀(∈). We prove similar statements for 2-connected and 3-connected planar graphs and maps.

langue originale	Anglais
Pages (de - à)	145-178
Nombre de pages	34
journal	Combinatorics Probability and Computing
Volume	24
Numéro de publication	1
Les DOIs	https://doi.org/10.1017/S0963548314000467
état	Publié - 12 janv. 2015

Accès au document

10.1017/S0963548314000467

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

@article{da408050a35c466e84531c397326a83e,

title = "On the diameter of random planar graphs",

abstract = "We show that the diameter diam(Gn) of a random labelled connected planar graph with n vertices is equal to n1/4+o(1), in probability. More precisely, there exists a constant c > 0 such that P(diam(Gn) ∈ (n1/4?∈, n1/4+∈)) ≥1 ? exp(?nc∈) for ∈ small enough and n ≥n0(∈). We prove similar statements for 2-connected and 3-connected planar graphs and maps.",

author = "Guillaume Chapuy and {\'E}ric Fusy and Omer Gim{\'e}nez and Marc Noy",

note = "Publisher Copyright: Copyright {\textcopyright} 2014 Cambridge University Press.",

year = "2015",

month = jan,

day = "12",

doi = "10.1017/S0963548314000467",

language = "English",

volume = "24",

pages = "145--178",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

number = "1",

}

TY - JOUR

T1 - On the diameter of random planar graphs

AU - Chapuy, Guillaume

AU - Fusy, Éric

AU - Giménez, Omer

AU - Noy, Marc

PY - 2015/1/12

Y1 - 2015/1/12

N2 - We show that the diameter diam(Gn) of a random labelled connected planar graph with n vertices is equal to n1/4+o(1), in probability. More precisely, there exists a constant c > 0 such that P(diam(Gn) ∈ (n1/4?∈, n1/4+∈)) ≥1 ? exp(?nc∈) for ∈ small enough and n ≥n0(∈). We prove similar statements for 2-connected and 3-connected planar graphs and maps.

AB - We show that the diameter diam(Gn) of a random labelled connected planar graph with n vertices is equal to n1/4+o(1), in probability. More precisely, there exists a constant c > 0 such that P(diam(Gn) ∈ (n1/4?∈, n1/4+∈)) ≥1 ? exp(?nc∈) for ∈ small enough and n ≥n0(∈). We prove similar statements for 2-connected and 3-connected planar graphs and maps.

UR - https://www.scopus.com/pages/publications/84927628168

U2 - 10.1017/S0963548314000467

DO - 10.1017/S0963548314000467

M3 - Article

AN - SCOPUS:84927628168

SN - 0963-5483

VL - 24

SP - 145

EP - 178

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 1

ER -

On the diameter of random planar graphs

Résumé

Accès au document

Autres fichiers et liens

Empreinte digitale

Contient cette citation