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.
Abstract
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
