Metadata only
Date
2005Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
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
Publication status
publishedExternal links
Book title
SODA '05: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete AlgorithmsPages / Article No.
Publisher
SIAMEvent
Organisational unit
03672 - Steger, Angelika / Steger, Angelika
More
Show all metadata
ETH Bibliography
yes
Altmetrics