Maximal biconnected subgraphs of random planar graphs

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. Denote by b (ℓ; C n ) the number of blocks (i.e., maximal biconnected subgraphs) of C n that contain exactly ℓ vertices, and let lb (C n ) be the number of vertices in a largest block of C n . We show that under certain general assumptions on C , C n belongs with high probability to one of the following categories: (1) lb (C n ) ∼ cn , for some explicitly given c = c ( C ), and the second largest block is of order n α , where 1 > α = α( C ), or (2) lb (C n ) = O (log n ), that is, all blocks contain at most logarithmically many vertices. Moreover, in both cases we show that the quantity b (ℓ; C n ) is concentrated for all ℓ and we determine its expected value. As a corollary we obtain that the class of planar graphs belongs to category (1). In contrast to that, outerplanar and series-parallel graphs belong to category (2).