Generating labeled planar graphs uniformly at random
From MaRDI portal
Publication:2373725
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
dynamic programming; decomposition; graph theory; enumeration; sampling algorithm; labeled planar graph
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, Phase transitions in graphs on orientable 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, The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation, An Experimental Study on Generating Planar Graphs, Uniform random sampling of planar graphs in linear time
Uses Software
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