Generating labeled planar graphs uniformly at random

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

  • Manuel Bodirsky - , Humboldt University of Berlin (Author)
  • Clemens Gröpl - (Author)
  • Mihyun Kang - (Author)

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 languageEnglish
Pages (from-to)377-386
Number of pages10
JournalTheoretical computer science : the journal of the EATCS
Volume379
Issue number3
Publication statusPublished - 15 Jun 2007
Peer-reviewedYes
Externally publishedYes

External IDs

Scopus 34248546188
ORCID /0000-0001-8228-3611/work/142241163

Keywords

Keywords

  • Decomposition, Dynamic programming, Enumeration, Graph theory, Labeled planar graph, Sampling algorithm