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: http://www.sciencedirect.com/science/article/B6V1G...

## Abstract

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