Repository: Freie Universität Berlin, Math Department

Generating labeled planar graphs uniformly at random

Bodirsky, M. and Gröpl, C. and Kang, M. (2003) Generating labeled planar graphs uniformly at random. In: Proceedings of ICALP 2003.

Full text not available from this repository.


We present an expected polynomial time algorithm to generate a labeled planar graph uniformly at random. To generate the planar graphs, we derive recurrence formulas that count all such graphs with n vertices and m edges, based on a decomposition into 1-, 2-, and 3-connected components. For 3-connected graphs we apply a recent random generation algorithm by Schaeffer and a counting formula by Mullin and Schellenberg.

Item Type:Conference or Workshop Item (UNSPECIFIED)
Additional Information:Appeared 2008 in Theoretical Computer Science. { The download is the journal submission <br> From time to time we receive requests for source code, so here it is: See the files BGK03b.README and GBK03b.tar.bz2 }
Uncontrolled Keywords:Planar Graph, Enumeration, Random graphs, Random Generation, 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:341
Deposited By: Admin Administrator
Deposited On:14 Apr 2009 14:37
Last Modified:14 Apr 2009 14:37

Repository Staff Only: item control page