Name
Abstract | ||
|---|---|---|
We consider random planar graphs on $n$ labelled nodes, and show in particular that if the graph is picked uniformly at random then the expected number of edges is at least $\frac{13}{7}n +o(n)$. To prove this result we give a lower bound on the size of the set of edges that can be added to a planar graph on $n$ nodes and $m$ edges while keeping it planar, and in particular we see that if $m$ is at most $\frac{13}{7}n - c$ (for a suitable constant~$c$) then at least this number of edges can be added. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1017/S0963548303005947 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
random planar graphs,expected number,random planar graph,planar graph,labelled node | Discrete mathematics,Graph,Combinatorics,Multigraph,Upper and lower bounds,Planar straight-line graph,Expected value,Planar,Multiple edges,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
13 | 2 | 0963-5483 |
Citations | PageRank | References |
17 | 12.38 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stefanie Gerke | 1 | 199 | 31.63 |
| Colin McDiarmid | 2 | 1071 | 167.05 |