Generating labeled planar graphs uniformly at random

DOI10.1016/J.TCS.2007.02.045MaRDI QIDQ2373725zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Clemens Gröpl, 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

decompositiondynamic programmingenumerationgraph theorylabeled planar graphsampling algorithm

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2038777
• Uniform random sampling of planar graphs in linear time
• Algorithms and Computation
• Generating Outerplanar Graphs Uniformly at Random
• scientific article; zbMATH DE number 5050599

Cites work

• A calculus for the random generation of labelled combinatorial structures
• A Census of Planar Maps
• Algorithms and Computation
• Asymptotic enumeration and limit laws of planar graphs
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Counting labelled three-connected and homeomorphically irreducible two- connected graphs
• Counting non-isomorphic three-connected planar maps
• Counting unlabelled three-connected and homeomorphically irreducible two- connected graphs
• Dissections and trees, with applications to optimal mesh encoding and to random sampling
• Generating Outerplanar Graphs Uniformly at Random
• scientific article; zbMATH DE number 3150821 (Why is no real title available?)
• scientific article; zbMATH DE number 4055646 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1025912 (Why is no real title available?)
• scientific article; zbMATH DE number 1146225 (Why is no real title available?)
• scientific article; zbMATH DE number 1962839 (Why is no real title available?)
• On random planar graphs, the number of planar graphs and their triangulations
• On the Number of Edges in Random Planar Graphs
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• Random planar graphs
• Random sampling of large planar maps and convex polyhedra
• The enumeration of c-nets via quadrangulations
• The On-Line Encyclopedia of Integer Sequences
• Uniform random generation of decomposable structures using floating-point arithmetic

Cited in

(21)

• 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
• The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation
• A direct decomposition of 3-connected planar graphs
• Random sampling of large planar maps and convex polyhedra
• An unbiased pointing operator for unlabeled structures, with applications to counting and sampling
• An experimental study on generating planar graphs
• Uniform random sampling of planar graphs in linear time
• scientific article; zbMATH DE number 15335 (Why is no real title available?)
• scientific article; zbMATH DE number 2038777 (Why is no real title available?)
• The Evolution of Random Graphs on Surfaces
• Phase transitions in graphs on orientable surfaces
• Logical properties of random graphs from small addable classes
• Generating unlabeled connected cubic planar graphs uniformly at random
• Generating Outerplanar Graphs Uniformly at Random
• scientific article; zbMATH DE number 5050599 (Why is no real title available?)
• Algorithms and Computation
• Subgraphs of 4-regular planar graphs
• Sampling unlabeled chordal graphs in expected polynomial time

Describes a project that uses

Uses Software

• OEIS

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373725)