Name
Abstract | ||
|---|---|---|
We consider the following variant of the classical random graph process introduced by Erdős and Rényi. Starting with an empty graph on n vertices, choose the next edge uniformly at random among all edges not yet considered, but only insert it if the graph remains planar. We show that for all ε 0, with high probability, &thetas;(n2) edges have to be tested before the number of edges in the graph reaches (1 + ε)n. At this point, the graph is connected with high probability and contains a linear number of induced copies of any fixed connected planar graph, the first property being in contrast and the second one in accordance with the uniform random planar graph model. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008 |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1002/rsa.v32:2 | Random Struct. Algorithms |
Keywords | Field | DocType |
random graph,planar graph | Strength of a graph,Discrete mathematics,Geometric graph theory,Combinatorics,Line graph,Cycle graph,Null graph,Butterfly graph,Mathematics,Voltage graph,Complement graph | Journal |
Volume | Issue | ISSN |
32 | 2 | 1042-9832 |
Citations | PageRank | References |
7 | 0.66 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stefanie Gerke | 1 | 199 | 31.63 |
| Dirk Schlatter | 2 | 21 | 1.71 |
| Angelika Steger | 3 | 995 | 111.50 |
| Anusch Taraz | 4 | 168 | 37.71 |