Generating Outerplanar Graphs Uniformly at random
By Manuel Bodirsky and Mihyun KangPresented at the 1st workshop on Algorithms for Listing, Counting, and Enumeration (ALICE03).
Combinatorics, Probability and Computing, 15 (2006), 333-343
Abstract
We show how to generate labeled and unlabeled outerplanar graphs with n vertices uniformly at random in (expected) polynomial time in n. To generate these graphs, we use the decomposition of a graph according to its block structure, and compute the exact number of labeled outerplanar graphs. This allows us to make the correct probabilistic choices in a recursive generation of uniformly distributed outerplanar graphs.
Next we modify our formulas to also count unlabeled rooted graphs, and finally show how to use these formulas in a Monte Carlo algorithm to generate unlabeled outerplanar graphs uniformly at random in expected polynomial time.
Download
- ps - outerplanar.ps
- pdf - outerplanar.pdf
Deutsch