Generating Outerplanar Graphs Uniformly at Random
Manuel Bodirsky, Mihyun Kang · Combinatorics Probability Computing · 2006
We show how to generate labelled and unlabelled outerplanar graphs with . To generate labelled outerplanar graphs, we present a counting technique using the decomposition of a graph according to its block structure, and compute the exact number of labelled 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 rooted unlabelled graphs, and finally show how to use these formulas in a Las Vegas algorithm to generate unlabelled outerplanar graphs uniformly at random in expected polynomial time.