Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9515950 | Journal of Combinatorial Theory, Series B | 2005 | 19 Pages |
Abstract
We study various properties of the random planar graph Rn, drawn uniformly at random from the class Pn of all simple planar graphs on n labelled vertices. In particular, we show that the probability that Rn is connected is bounded away from 0 and from 1. We also show for example that each positive integer k, with high probability Rn has linearly many vertices of a given degree, in each embedding Rn has linearly many faces of a given size, and Rn has exponentially many automorphisms.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Colin McDiarmid, Angelika Steger, Dominic J.A. Welsh,