Generating labeled planar graphs uniformly at random
Research output: Contribution to journal › Research article › Contributed › peer-review
Contributors
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. © 2007 Elsevier Ltd. All rights reserved.
Details
Original language | English |
---|---|
Pages (from-to) | 377-386 |
Number of pages | 10 |
Journal | Theoretical computer science : the journal of the EATCS |
Volume | 379 |
Issue number | 3 |
Publication status | Published - 15 Jun 2007 |
Peer-reviewed | Yes |
Externally published | Yes |
External IDs
Scopus | 34248546188 |
---|---|
ORCID | /0000-0001-8228-3611/work/142241163 |
Keywords
Keywords
- Decomposition, Dynamic programming, Enumeration, Graph theory, Labeled planar graph, Sampling algorithm