Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-25T19:27:37.453Z Has data issue: false hasContentIssue false
  • English
  • Français

Generating Outerplanar Graphs Uniformly at Random

Published online by Cambridge University Press:  07 April 2006

MANUEL BODIRSKY  and
MIHYUN KANG
MANUEL BODIRSKY
Affiliation:
Humboldt-Universität zu Berlin, Germany (e-mail: [email protected], [email protected])
MIHYUN KANG
Affiliation:
Humboldt-Universität zu Berlin, Germany (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 15 , Issue 3 , May 2006 , pp. 333 - 343
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)