Generating Outerplanar Graphs Uniformly at Random

This publication is with permission of the rights owner freely accessible due to an Alliance licence and a national licence (funded by the DFG, German Research Foundation) respectively.We show how to generate labelled and unlabelled outerplanar graphs with $n$ vertices uniformly at random in polynomial time in $n$. 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.Peer Reviewe