On the Diameter of Random Planar Graphs

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Other literature type 01 Jan 2010Embargo end date: 01 Jan 2012 English Publisher:Cambridge University Press (CUP)Journal:Combinatorics, Probability and Computing, volume 24, pages 145-178 (issn: 0963-5483, eissn: 1469-2163,

Copyright policy )Funded by:EC | EXPLOREMAPS

Authors: Chapuy, G.; Fusy, Éric; Giménez Llach, Omer; Noy Serrano, Marcos;

doi: 10.1017/s0963548314000467 , 10.46298/dmtcs.2790 , 10.48550/arxiv.1203.3079

arXiv: 1203.3079

handle: 2117/28378

On the Diameter of Random Planar Graphs

- Summary
- Subjects
- Metrics

Abstract

We show that the diameter diam(Gn) of a random labelled connected planar graph withnvertices is equal ton1/4+o(1), in probability. More precisely, there exists a constantc> 0 such that$$ P(\D(G_n)\in(n^{1/4-\e},n^{1/4+\e}))\geq 1-\exp(-n^{c\e}) $$for ε small enough andn ≥ n0(ε). We prove similar statements for 2-connected and 3-connected planar graphs and maps.

Related Organizations

Universitat Politècnica de Catalunya
Spain
Universitat Polite`cnica de Catalunya
Spain
Laboratoire d'informatique
France
LABORATOIRE D'INFORMATIQUE
France
CENTRE NATIONAL DE LA RECHERCHE SCIENTIFIQUE
France

View all View all

Keywords

Random graphs (graph-theoretic aspects), planar graph, Classificació AMS::05 Combinatorics::05C Graph theory, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Random graph, Enumeration in graph theory, Planar graphs; geometric and topological aspects of graph theory, Graph labelling (graceful graphs, bandwidth, etc.), [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, diameter, Connectivity, singularity analysis, Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], bivariate generating functions, [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], Combinatorics (math.CO), :05 Combinatorics::05C Graph theory [Classificació AMS], :Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs [Àrees temàtiques de la UPC]

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	13
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average