Uniform random sampling of planar graphs in linear time
From MaRDI portal
Abstract: This article introduces new algorithms for the uniform random generation of labelled planar graphs. Its principles rely on Boltzmann samplers, as recently developed by Duchon, Flajolet, Louchard, and Schaeffer. It combines the Boltzmann framework, a suitable use of rejection, a new combinatorial bijection found by Fusy, Poulalhon and Schaeffer, as well as a precise analytic description of the generating functions counting planar graphs, which was recently obtained by Gim'enez and Noy. This gives rise to an extremely efficient algorithm for the random generation of planar graphs. There is a preprocessing step of some fixed small cost. Then, the expected time complexity of generation is quadratic for exact-size uniform sampling and linear for approximate-size sampling. This greatly improves on the best previously known time complexity for exact-size uniform sampling of planar graphs with vertices, which was a little over .
Recommendations
- On the Complexity of Sampling Vertices Uniformly from a Graph
- On random sampling in uniform hypergraphs
- Sampling geometric inhomogeneous random graphs in linear time
- On sampling simple paths in planar graphs according to their lengths
- A linear-time algorithm for sampling graphs with given degrees
- Uniform sampling of digraphs with a fixed degree sequence
- Uniform sampling of bipartite graphs with degrees in prescribed intervals
- scientific article; zbMATH DE number 2038777
- Generating labeled planar graphs uniformly at random
- Uniform sampling of directed and undirected graphs conditional on vertex connectivity
Cites work
- scientific article; zbMATH DE number 3535592 (Why is no real title available?)
- scientific article; zbMATH DE number 1111371 (Why is no real title available?)
- scientific article; zbMATH DE number 5050599 (Why is no real title available?)
- scientific article; zbMATH DE number 3236772 (Why is no real title available?)
- 2-Isomorphic Graphs
- A Census of Planar Maps
- A bijection for triangulations of a polygon with interior points and multiple edges
- A calculus for the random generation of labelled combinatorial structures
- Analytic combinatorics
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- Boltzmann oracle for combinatorial systems
- Counting labelled three-connected and homeomorphically irreducible two- connected graphs
- Degree distribution in random planar graphs
- Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling
- Finite Continuous Time Markov Chains
- Generating labeled planar graphs uniformly at random
- Optimal coding and sampling of triangulations
- Planar graphs, via well-orderly maps and trees
- Planar maps as labeled mobiles
- Random planar graphs
- Random planar graphs with \(n\) nodes and a fixed number of edges
- Singularity Analysis of Generating Functions
- The asymptotic enumeration of rooted convex polyhedra
- The enumeration of c-nets via quadrangulations
- The number of labeled 2-connected planar graphs
- Transversal structures on triangulations: A combinatorial study and straight-line drawings
- Uniform random generation of decomposable structures using floating-point arithmetic
Cited in
(31)- On random sampling in uniform hypergraphs
- scientific article; zbMATH DE number 5050599 (Why is no real title available?)
- Random sampling of large planar maps and convex polyhedra
- The evolution of random graphs on surfaces
- Random graphs from a weighted minor-closed class
- Analytic combinatorics of chord and hyperchord diagrams with k crossings
- Properties of random graphs via Boltzmann samplers
- Random planar maps and graphs with minimum degree two and three
- scientific article; zbMATH DE number 15335 (Why is no real title available?)
- Generating labeled planar graphs uniformly at random
- Degree distribution in random planar graphs
- Intruder alert! Optimization models for solving the mobile robot graph-clear problem
- A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings
- Exact-Size Sampling of Enriched Trees in Linear Time
- Phase transitions in graphs on orientable surfaces
- Explore and repair graphs with black holes using mobile entities
- Algorithms and Computation
- The Evolution of Random Graphs on Surfaces
- On the Complexity of Sampling Vertices Uniformly from a Graph
- A bijection for plane graphs and its applications
- Concentration of maximum degree in random planar graphs
- scientific article; zbMATH DE number 2038777 (Why is no real title available?)
- The maximum degree of random planar graphs
- Uniform random sampling of simple branched coverings of the sphere by itself
- Random-bit optimal uniform sampling for rooted planar trees with given sequence of degrees and applications
- Generating unlabeled connected cubic planar graphs uniformly at random
- Classes of graphs embeddable in order-dependent surfaces
- A linear algorithm for the random sampling from regular languages
- Generating Outerplanar Graphs Uniformly at Random
- Scalable Uniform Graph Sampling by Local Computation
- An experimental study on generating planar graphs
This page was built for publication: Uniform random sampling of planar graphs in linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3055787)
