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