Hostname: page-component-745bb68f8f-b95js Total loading time: 0 Render date: 2025-02-05T20:59:36.893Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Diameter of Random Planar Graphs

Published online by Cambridge University Press:  18 September 2014

GUILLAUME CHAPUY ,
ÉRIC FUSY ,
OMER GIMÉNEZ  and
MARC NOY
GUILLAUME CHAPUY
Affiliation:
CNRS, LIAFA, UMR 7089, Université Paris Diderot–Paris 7, Case 7014, 75205 Paris CEDEX 13, France (e-mail: guillaume.chapuy@liafa.univ-paris-diderot.fr)
ÉRIC FUSY
Affiliation:
CNRS, LIX, UMR 7161, École Polytechnique, 91128 Palaiseau CEDEX, France (e-mail: fusy@lix.polytechnique.fr)
OMER GIMÉNEZ
Affiliation:
Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Barcelona, Spain (e-mail: omer.gimenez@gmail.com)
MARC NOY
Affiliation:
Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Barcelona, Spain (e-mail: marc.noy@upc.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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(\D(G_n)\in(n^{1/4-\e},n^{1/4+\e}))\geq 1-\exp(-n^{c\e}) $$
for ε small enough and n ≥ n0(ε). We prove similar statements for 2-connected and 3-connected planar graphs and maps.

Keywords

Primary 05C80Secondary 05C3005A1682B4168Q87
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Special Issue 1: Honouring the Memory of Philippe Flajolet - Part 3 , January 2015 , pp. 145 - 178
Copyright
Copyright © Cambridge University Press 2014 

References

[1] Albenque, M. and Marckert, J. F. (2008) Some families of increasing planar maps. Electron. J. Probab. 13 1624–1671.Google Scholar
[2] Ambjørn, J. and Budd, T. (2013) Trees and spatial topology change in CDT. J. Phys. A: Math. Theor. 46 315201.CrossRefGoogle Scholar
[3] Arquès, D. (1985) Une relation fonctionnelle nouvelle sur les cartes planaires pointées. J. Combin. Theory Ser. B 39 27–42.Google Scholar
[4] Banderier, C., Flajolet, P., Schaeffer, G. and Soria, M. (2001) Random maps, coalescing saddles, singularity analysis, and Airy phenomena. Random Struct. Alg. 19 194–246.Google Scholar
[5] Bender, E. A., Canfield, E. R. and Richmond, L. B. (1993) The asymptotic number of rooted maps on surfaces II: Enumeration by vertices and faces. J. Combin. Theory Ser. A 63 318–329.Google Scholar
[6] Bender, E., Gao, Z. and Wormald, N. (2002) The number of labeled 2-connected planar graphs. Electron. J. Combin. 9 1–13.Google Scholar
[7] Bouttier, J., Di Francesco, P. and Guitter, E. (2002) Census of planar maps: From the one-matrix model solution to a combinatorial proof. Nucl. Phys. B645 477–499.CrossRefGoogle Scholar
[8] Bouttier, J., Di Francesco, P. and Guitter, E. (2003) Geodesic distance in planar graphs. Nucl. Phys. B663 535–567.Google Scholar
[9] Chapuy, G., Marcus, M. and Schaeffer, G. (2009) A bijection for rooted maps on orientable surfaces. SIAM J. Discrete Math. 23 1587–1611.Google Scholar
[10] Chassaing, P. and Schaeffer, G. (2004) Random planar lattices and integrated superBrownian excursion. Probab. Theory Rel. Fields 128 161–212.CrossRefGoogle Scholar
[11] Cori, R. and Vauquelin, B. (1981) Planar maps are well labeled trees. Canad. J. Math. 33 1023–1042.Google Scholar
[12] Drmota, M., Giménez, O. and Noy, M. (2011) The maximum degree of series-parallel graphs. Combin. Probab. Comput. 20 529–570.Google Scholar
[13] Drmota, M., Giménez, O., Noy, M., Panagiotou, K. and Steger, A. (2012) The maximum degree of random planar graphs. In SODA 2012, pp. 281–287.Google Scholar
[14] Flajolet, P., Gao, Z., Odlyzko, A. M. and Richmond, L. B. (1993) The distribution of heights of binary trees and other simple trees. Combin. Probab. Comput. 2 145–156.CrossRefGoogle Scholar
[15] Le Gall, J. F. (1999) Spatial Branching Processes, Random Snakes and Partial Differential Equations, Lectures in Mathematics, ETH Zürich, Birkhäuser.Google Scholar
[16] Le Gall, J. F. (2007) The topological structure of scaling limits of large planar maps. Invent. Math. 169 621–670.Google Scholar
[17] Le Gall, J. F. and Paulin, F. (2008) Scaling limits of bipartite planar maps are homeomorphic to the 2-sphere. Geom. Funct. Anal. 18 893–918.Google Scholar
[18] Le Gall, J. F. (2013) Uniqueness and universality of the Brownian map. Ann. Probab. 41 2880–2960.Google Scholar
[19] Gao, J. and Wormald, N. (1999) The size of the largest components in random planar maps. SIAM J. Discrete Math. 12 217–228.Google Scholar
[20] Giménez, O. and Noy, M. (2009) Asymptotic enumeration and limit laws of planar graphs. J. Amer. Math. Soc. 22 309–329.Google Scholar
[21] Giménez, O. and Noy, M. (2009) Counting planar graphs and related families of graphs. In Surveys in Combinatorics 2009, Cambridge University Press, pp. 169–210.Google Scholar
[22] Giménez, O., Noy, M. and Rué, J. (2013) Graph classes with given 3-connected components: asymptotic enumeration and random graphs. Random Struct. Alg. 42 (4) 438–479.Google Scholar
[23] Hopcroft, J. and Tarjan, R. E. (1973) Dividing a graph into triconnected components. SIAM J. Comput. 2 135–158.Google Scholar
[24] Marckert, J. F. and Miermont, G. (2007) Invariance principles for random bipartite planar maps. Ann. Probab. 35 1642–1705.Google Scholar
[25] Marckert, J. F. and Mokkadem, A. (2006) Limit of normalized random quadrangulations: The Brownian map. Ann. Probab. 34 2144–2202.CrossRefGoogle Scholar
[26] Miermont, G. (2006) An invariance principle for random planar maps. In Fourth Colloquium in Mathematics and Computer Sciences: CMCS'06, DMTCS Proc. AG, pp. 39–58.CrossRefGoogle Scholar
[27] Miermont, G. (2008) On the sphericity of scaling limits of random planar quadrangulations. Electron. Comm. Probab. 13 248–257.CrossRefGoogle Scholar
[28] Miermont, G. (2013) The Brownian map is the scaling limit of uniform random plane quadrangulations. Acta Math. 210 319–401.Google Scholar
[29] Mohar, B. and Thomassen, C. (2001) Graphs on Surfaces, John Hopkins University Press.Google Scholar
[30] Panagiotou, K. and Steger, A. (2010) Maximal biconnected subgraphs of random planar graphs. ACM Trans. Algorithms 6 #31.Google Scholar
[31] Schaeffer, G. (1998) Conjugaison d'arbres et cartes combinatoires aléatoires. PhD thesis, Université Bordeaux I.Google Scholar
[32] Tutte, W. T. (1963) A census of planar maps. Canad. J. Math. 15 249–271.Google Scholar
[33] Tutte, W. T. (1966) Connectivity in Graphs, Oxford University Press.Google Scholar
[34] Walsh, T. R. S. (1982) Counting labeled three-connected and homeomorphically irreducible two-connected graphs. J. Combin. Theory Ser. B 32 1–32.Google Scholar