Generating labeled planar graphs uniformly at random

DOI10.1016/j.tcs.2007.02.045zbMath1121.68085MaRDI 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 programming; decomposition; graph theory; enumeration; sampling algorithm; labeled planar graph

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

The Evolution of Random Graphs on Surfaces, Logical properties of random graphs from small addable classes, Subgraphs of 4-regular planar graphs, The evolution of random graphs on surfaces, Symmetries of unlabelled planar triangulations, Logical limit laws for minor-closed classes of graphs, Tabu search for the BWC problem, An Experimental Study on Generating Planar Graphs, Uniform random sampling of planar graphs in linear time

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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