No CrossRef data available.
Published online by Cambridge University Press: 03 March 2004
We consider random planar graphs on $n$ labelled nodes, and show in particular that if the graph is picked uniformly at random then the expected number of edges is at least $\frac{13}{7}n +o(n)$. To prove this result we give a lower bound on the size of the set of edges that can be added to a planar graph on $n$ nodes and $m$ edges while keeping it planar, and in particular we see that if $m$ is at most $\frac{13}{7}n - c$ (for a suitable constant~$c$) then at least this number of edges can be added.