

(LaTeX) Abstract: 
Let $\mathcal{C}$ be a class of labeled connected graphs, and let $C_n$ be a graph drawn uniformly at random from graphs in $\mathcal{C}$ that contain exactly $n$ vertices. Denote by~$b(\ell;\, C_n)$ the number of blocks (i.e.\ maximal biconnected subgraphs) of~$C_n$ that contain exactly~$\ell$ 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~$\mathcal{C}$, $C_n$ belongs with high probability to one of the following categories:
\begin{itemize}
\item[(1)] $lb(C_n) \sim cn$, for some explicitly given $c = c(\mathcal{C})$, and the second largest block is of order $n^{\alpha}$, where $1 > \alpha = \alpha(\mathcal{C})$, or
\item[(2)] $lb(C_n) = \mathcal{O}(\log n)$, i.e., all blocks contain at most logarithmically many vertices.
\end{itemize}
Moreover, in both cases we show that the quantity $b(\ell;\, C_n)$ is concentrated for all $\ell$, 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 seriesparallel graphs belong to category~(2). 
Keywords: 
Graphs with Constraints, Planar Graphs, Random Structures 




Download
Access Level: 
Public 
