Random planar graphs

Marc Noy¹

Universitat Politècnica de Catalunya

Let $G$ be a graph chosen uniformly at random among all labelled planar graphs with $n$ vertices. Which are the typical properties of such a random planar graph?

We show that $G$ has about $Cn$ edges, where $C = 2.21326\dots$ is a constant completely determined, and that deviations from $Cn$ are with high probability of small order. Among other properties, we also show that $G$ is connected with probability tending to a constant $0.96325\dots$

The basic technique we use in the proofs is singularity analysis of counting generating functions, considered as complex valued functions.

Footnotes

... Noy¹

joint work with Omer Gimenez