No CrossRef data available.
Article contents
On the Diameter of Random Planar Graphs
Published online by Cambridge University Press: 18 September 2014
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 for ε small enough and n ≥ n0(ε). We prove similar statements for 2-connected and 3-connected planar graphs and maps.
$$P(\D(G_n)\in(n^{1/4-\e},n^{1/4+\e}))\geq 1-\exp(-n^{c\e})$$
Information
- 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
[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
You have
Access
- 11
- Cited by