Name
Abstract | ||
|---|---|---|
Let the random graph Rn be drawn uniformly at random from the set of all simple planar graphs on n labelled vertices. We see that with high probability the maximum degree of Rn is Θ(ln n). We consider also the maximum size of a face and the maximum increase in the number of components on deleting a vertex. These results extend to graphs embeddable on any fixed surface. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1017/S0963548308009097 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
random graph,graphs embeddable,maximum degree,high probability,random planar graph,fixed surface,simple planar graph,ln n,maximum increase,n labelled vertex,maximum size,planar graph | Discrete mathematics,Random regular graph,Outerplanar graph,Combinatorics,Random graph,Cycle graph,Book embedding,Degree (graph theory),1-planar graph,Mathematics,Planar graph | Journal |
Volume | Issue | ISSN |
17 | 4 | 0963-5483 |
Citations | PageRank | References |
12 | 0.78 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin McDiarmid | 1 | 1071 | 167.05 |
| Bruce Reed | 2 | 305 | 16.94 |