Repository: Freie Universität Berlin, Math Department

Generating labeled planar graphs uniformly at random

Bodirsky, M. and Gröpl, C. and Kang, M. (2007) Generating labeled planar graphs uniformly at random. Theoretical Computer Science, 379 (3). pp. 377-386.

Full text not available from this repository.

Official URL:


We present a deterministic polynomial time algorithm to sample a labeled planar graph uniformly at random. Our approach uses recursive formulae for the exact number of labeled planar graphs with n vertices and m edges, based on a decomposition into 1-, 2-, and 3-connected components. We can then use known sampling algorithms and counting formulae for 3-connected planar graphs.

Item Type:Article
Uncontrolled Keywords:Labeled planar graph, Enumeration, Decomposition, Sampling algorithm, Dynamic programming, Graph theory
Subjects:Mathematical and Computer Sciences > Computer Science
Divisions:Department of Mathematics and Computer Science > Institute of Computer Science > Algorithmic Bioinformatics Group
ID Code:339
Deposited By: Admin Administrator
Deposited On:14 Apr 2009 14:19
Last Modified:14 Apr 2009 14:19

Repository Staff Only: item control page