Random planar graphs with n nodes and a fixed number of edges
Stefanie Gerke, Colin McDiarmid, Angelika Steger, Andreas Weißl · 2005
Let P(n,m) be the class of simple labelled planar graphs with n nodes and m edges, and let Rn,q be a graph drawn uniformly at random from P(n, bqnc). We show properties that hold with high probability (w.h.p.) for Rn,q when 1 < q < 3. For example, we show that Rn,q contains w.h.p. linearly many nodes of each given degree and linearly many node disjoint copies of each given fixed connected planar graph. Additionally, we show that the probability that Rn,q is connected is bounded away from one by a non-zero constant. As a tool we show that (|P(n, bqnc)|/n!)1/n tends to a limit as n tends to infinity. 1