Analysis of Complex Networks

17.5 Planar Graphs

The counting problem of several classes of planar graphs resp. planar maps goes back to Tutte [8, 36, 37]. Interestingly enough, the study of random vertex labeled planar graphs is a recent one. Random planar graphs were introduced by Denise et al. [13], and since then they have been widely studied. Several natural parameters defined on R_n have been studied, starting with the number of edges, which is probably the most basic one. Partial results were obtained in [7, 13, 25, 34], until it was shown by Giménez and Noy [26] that the number of edges in random planar graphs obeys asymptotically a normal limit law with linear expectation and variance. The expectation is asymptotically κn, where κ ≈ 2.21326 is a well-defined analytic constant. This implies that the average degree of the vertices is 2κ ≈ 4.42652. McDiarmid et al. showed that with high probability a planar graph has a linear number of vertices of degree k, for each k ≥ 1 [32].

In what follows we present here an approach to random (vertex) labeled planar graphs that is based on GFs and indicate how corresponding counting problems and distributional results can be obtained. We recall that a graph is 2-connected if it is connected and one has to remove at least two vertices (and all incident edges) to disconnect it. Similarly, a graph is 3-connected if it is 2-connected and one has to remove at least three vertices to disconnect.

We first provide a system of equations for the corresponding GFs (see [4, 26]). ...