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. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1016/j.jctb.2004.09.007 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
high probability,planar,embedding rn,random,class pn,counting,n labelled vertex,labelled,positive integer k,various property,graph,random planar graph,simple planar graph,planar graph | Discrete mathematics,Random regular graph,Combinatorics,Outerplanar graph,Random graph,Graph embedding,Polyhedral graph,Planar straight-line graph,Book embedding,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
93 | 2 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
49 | 5.07 | 8 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Colin McDiarmid | 1 | 1071 | 167.05 |
Angelika Steger | 2 | 995 | 111.50 |
Dominic J. A. Welsh | 3 | 83 | 10.91 |