Author
Gerke, S
McDiarmid, C
Steger, A
Weißl, A
Journal title
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Last updated
2021-10-19T13:19:03.233+01:00
Page
999-1007
Abstract
Let ℘(n, m) be the class of simple labelled planar graphs with n nodes and m edges, and let Rn,q be a graph drawn uniformly at random from ℘(n, ⌊qn⌋). We show properties that hold with high probability (w.h.p.) for Rn,q when 1 < q < 3. For example, we show that Rn,q contains w.h.p. linearly many nodes of each given degree and linearly many node disjoint copies of each given fixed connected planar graph. Additionally, we show that the probability that Rn,q is connected is bounded away from one by a non-zero constant. As a tool we show that (|℘(n, ⌊qn⌋)|/n!)1/n tends to a limit as n tends to infinity.
Symplectic ID
102279
Publication type
Conference Paper
ISBN-13
978-0-89871-585-9
Publication date
1 July 2005
Please contact us with feedback and comments about this page.