Name
Abstract | ||
|---|---|---|
Let Pn be the class of all planar graphs with n labeled vertices, and let Pn be a graph drawn uniformly at random from Pn. In this paper we study the degree sequence of Pn. We show that with probability 1 -- o(1) the number of vertices of degree k in Pn is very close to a quantity μkn that we determine explicitly, for all k ≤ c log n and an appropriate c 0. A similar statement is true for random biconnected planar graphs as well. The main tool in our analysis is a framework that allows us under certain conditions to derive universal results about the degree distribution of random graphs from general classes with structural constraints. In particular, we address so-called critical graph classes, which due to their intricate structure have posed significant technical difficulties in the past. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.5555/2133036.2133127 | SODA |
Keywords | Field | DocType |
random graph,degree sequence,degree distribution,so-called critical graph class,degree k,random planar graph,planar graph,appropriate c,certain condition,log n,random biconnected planar graph,distributed computing,leader election,randomized algorithms | Discrete mathematics,Random regular graph,Outerplanar graph,Combinatorics,Indifference graph,Random graph,Chordal graph,Book embedding,Universal graph,1-planar graph,Mathematics | Conference |
ISBN | Citations | PageRank |
978-1-61197-251-1 | 3 | 0.41 |
References | Authors | |
13 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Konstantinos Panagiotou | 1 | 290 | 27.80 |
| Angelika Steger | 2 | 995 | 111.50 |