Generating labeled planar graphs uniformly at random

DOI10.1016/j.tcs.2007.02.045zbMath1121.68085OpenAlexW2069650246MaRDI QIDQ2373725

Clemens Gröpl, Manuel Bodirsky, Mihyun Kang

Publication date: 16 July 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.045

zbMATH Keywords

dynamic programmingdecompositiongraph theoryenumerationsampling algorithmlabeled planar graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Logical properties of random graphs from small addable classes ⋮ Tabu search for the BWC problem ⋮ The evolution of random graphs on surfaces ⋮ Symmetries of unlabelled planar triangulations ⋮ The Evolution of Random Graphs on Surfaces ⋮ Subgraphs of 4-regular planar graphs ⋮ Phase transitions in graphs on orientable surfaces ⋮ An Experimental Study on Generating Planar Graphs ⋮ Logical limit laws for minor-closed classes of graphs ⋮ The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation ⋮ Uniform random sampling of planar graphs in linear time

Uses Software

• OEIS

Cites Work

• Counting non-isomorphic three-connected planar maps
• Counting labelled three-connected and homeomorphically irreducible two- connected graphs
• Counting unlabelled three-connected and homeomorphically irreducible two- connected graphs
• Uniform random generation of decomposable structures using floating-point arithmetic
• A calculus for the random generation of labelled combinatorial structures
• On random planar graphs, the number of planar graphs and their triangulations
• Random planar graphs
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• Random sampling of large planar maps and convex polyhedra
• Asymptotic enumeration and limit laws of planar graphs
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• On the Number of Edges in Random Planar Graphs
• Generating Outerplanar Graphs Uniformly at Random
• The enumeration of c-nets via quadrangulations
• A Census of Planar Maps
• Algorithms and Computation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Generating labeled planar graphs uniformly at random