Uniform random planar graphs with degree constraints - Dowden, C (2008)
Random planar graphs have been the subject of much recent work. Many basic properties of the standard uniform random planar graph $P_{n}$, by which we mean a graph chosen uniformly at random from the set of all planar graphs with vertex set $ { 1,2, ldots, n }$, are now known, and variations on this standard random graph are also attracting interest. Prominent among the work on $P_{n}$ have been asymptotic results for the probability that $P_{n}$ will be connected or contain given components/ subgraphs. Such progress has been achieved through a combination of counting arguments citemcd and a generating function approach citegim. More recently, attention has turned to $P_{n,m}$, the graph taken uniformly at random from the set of all planar graphs on ${ 1,2, ldots, n }$ with exactly $m(n)$ edges (this can be thought of as a uniform random planar graph with a constraint on the average degree). In citeger and citegim, the case when $m(n) =~!lfloor qn floor$ for fixed $q in (1,3)$ has been investigated, and results obtained for the events that $P_{n, lfloor qn floor}$ will be connected and that $P_{n, lfloor qn floor}$ will contain given subgraphs. In Part I of this thesis, we use elementary counting arguments to extend the current knowledge of $P_{n,m}$. We investigate the probability that $P_{n,m}$ will contain given components, the probability that $P_{n,m}$ will contain given subgraphs, and the probability that $P_{n,m}$ will be connected, all for general $m(n)$, and show that there is different behaviour depending on which `region' the ratio $rac{m(n)}{n}$ falls into. In Part II, we investigate the same three topics for a uniform random planar graph with constraints on the maximum and minimum degrees.