Premium
The random planar graph process
Author(s) -
Gerke Stefanie,
Schlatter Dirk,
Steger Angelika,
Taraz Anusch
Publication year - 2008
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20186
Subject(s) - combinatorics , planar graph , mathematics , random graph , discrete mathematics , null graph , complement graph , graph , butterfly graph , random regular graph , line graph , voltage graph , 1 planar graph
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, θ ( n 2 ) 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