- Conference Paper
Let P(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 P(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 (|P(n, [qn])|/n!)1/n tends to a limit as n tends to infinity. Show more
Book titleSODA '05: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Pages / Article No.
Organisational unit03672 - Steger, Angelika / Steger, Angelika
MoreShow all metadata