Maximal biconnected subgraphs of random planar graphs

ABSTRACT

Let P_n be the class of simple labeled planar graphs with n vertices, and denote by P_n a graph drawn uniformly at random from this set. Basic properties of P_n were first investigated by Denise, Vasconcellos, and Welsh [7]. Since then, the random planar graph has attracted considerable attention, and is nowadays an important and challenging model for evaluating methods that are developed to study properties of random graphs from classes with structural side constraints.

In this paper we study closely the structure of P_n. More precisely, let b(l; P_n) be the number of blocks (i.e. maximal biconnected subgraphs) of P_n that contain exactly l vertices, and let lb(P_n) be the number of vertices in the largest block of P_n. We show that with high probability P_n contains a giant block that includes up to lower order terms cn vertices, where c ≈ 0.959 is an analytically given constant. Moreover, we show that the second largest block contains only [EQUATION] vertices, and prove sharp concentration results for b(l; P_n), for all 2 ≤ l ≤ n^2/3 (here [EQUATION](.) stands for "up to logarithmic factors").

In fact, we obtain this result as a consequence of a much more general result that we prove in this paper. Let C be a class of labeled connected graphs, and let C_n be a graph drawn uniformly at random from graphs in C that contain exactly n vertices. Under certain assumptions on C, and depending on the behavior of the singularity of the generating function enumerating the elements of C, C_n belongs with high probability to one of the following three categories, which differ vastly in complexity. C_n either

(1) behaves like a random planar graph, i.e. lb(C_n) ~ cn, for some analytically given c = c(C), and the second largest block is of order n^α, where 1 > α = α(C), or

(2) lb(C_n) = O(log n), i.e., all blocks contain at most logarithmically many vertices, or

(3) lb(C_n) = Õ(n^α), for some α = α(C) < 1.

Planar graphs belong to category (1). In contrast to that, outerplanar and series-parallel graphs belong to category (2).

REFERENCES

• 1: Cyril Banderier , Philippe Flajolet , Gilles Schaeffer , Michèle Soria, Random maps, coalescing saddles, singularity analysis, and airy phenomena, Random Structures & Algorithms, v.19 n.3-4, p.194-246, October-December 2001 [doi>10.1002/rsa.10021]
• 2: E. A. Bender, Z. Gao, and N. C. Wormald. The number of labeled 2-connected planar graphs. Electronic Journal of Combinatorics, 9(1):Research Paper 43, 13 pp. (electronic), 2002.
• 3: Edward A. Bender , L. Bruce Richmond , Nicholas C. Wormald, Largest 4-connected components of 3-connected planar triangulations, Random Structures & Algorithms, v.7 n.4, p.273-285, Dec. 1995 [doi>10.1002/rsa.3240070402]
• 4: Nicla Bernasconi , Konstantinos Panagiotou , Angelika Steger, On properties of random dissections and triangulations, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.132-141, January 20-22, 2008, San Francisco, California
• 5: Nicla Bernasconi , Konstantinos Panagiotou , Angelika Steger, On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs, Proceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, August 25-27, 2008, Boston, MA, USA [doi>10.1007/978-3-540-85363-3_25]
• 6: M. Bodirsky, O. Giménez, M. Kang, and M. Noy. On the number of series parallel and outerplanar graphs. In EuroComb '05, volume AE of DMTCS Proceedings, pages 383--388.
• 7: A. Denise, M. Vasconcellos, and D. J. A. Welsh. The random planar graph. Congressus Numerantium, 113:61--79, 1996.
• 8: Philippe Duchon , Philippe Flajolet , Guy Louchard , Gilles Schaeffer, Boltzmann Samplers for the Random Generation of Combinatorial Structures, Combinatorics, Probability and Computing, v.13 n.4-5, p.577-625, July 2004 [doi>10.1017/S0963548304006315]
• 9: P. Erdős and A. Rényi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl., 5:17--61, 1960.
• 10: Philippe Flajolet , Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, New York, NY, 2009
• 11: É. Fusy. Quadratic exact size and linear approximate size random generation of planar graphs. In Conrado Martnez, editor, 2005 International Conference on Analysis of Algorithms, volume AD of DMTCS Proceedings, pages 125--138.
• 12: Zhicheng Gao , Nicholas C. Wormald, The Size of the Largest Components in Random Planar Maps, SIAM Journal on Discrete Mathematics, v.12 n.2, p.217-228, 1999 [doi>10.1137/S0895480195292053]
• 13: O. Giménez and M. Noy. The number of planar graphs and properties of random planar graphs. In 2005 International Conference on Analysis of Algorithms, Discrete Math. Theor. Comput. Sci. Proc., AD, pages 147--156 (electronic). Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2005.
• 14: F. Harary and E. M. Palmer. Graphical Enumeration. Academic Press, New York, 1973.
• 15: Colin McDiarmid , Angelika Steger , Dominic J. A. Welsh, Random planar graphs, Journal of Combinatorial Theory Series B, v.93 n.2, p.187-205, March 2005 [doi>10.1016/j.jctb.2004.09.007]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory