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)
Universidad Politecnica de Catalunia

Research output: Contribution to journal › Article › peer-review

12 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	145-178
Number of pages	34
Journal	Combinatorics Probability and Computing
Volume	24
Issue number	1
DOIs	https://doi.org/10.1017/S0963548314000467
Publication status	Published - 12 Jan 2015

Access to Document

10.1017/S0963548314000467

Cite this

@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",

publisher = "Cambridge University Press",

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

Abstract

Access to Document

Other files and links

Fingerprint

Cite this