Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-29T08:50:13.614Z 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: [email protected])
ÉRIC FUSY
Affiliation:
CNRS, LIX, UMR 7161, École Polytechnique, 91128 Palaiseau CEDEX, France (e-mail: [email protected])
OMER GIMÉNEZ
Affiliation:
Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Barcelona, Spain (e-mail: [email protected])
MARC NOY
Affiliation:
Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Barcelona, Spain (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

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(\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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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