Uniform random sampling of planar graphs in linear time

DOI10.1002/RSA.20275MaRDI QIDQ3055787zbMATH OpenOpenAlexFDO

Authors Éric Fusy

Publication date 9 November 2010

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0705.1287

zbMATH Keywords

Boltzmann samplingplanar graphsrandom generation

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

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 $n$ vertices, which was a little over $O(n^7)$.

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

• 2-Isomorphic Graphs
• A bijection for triangulations of a polygon with interior points and multiple edges
• A calculus for the random generation of labelled combinatorial structures
• A Census of Planar Maps
• Analytic combinatorics
• Boltzmann oracle for combinatorial systems
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• 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
• 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?)
• 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

(33)

• Intruder alert! Optimization models for solving the mobile robot graph-clear problem
• The evolution of random graphs on surfaces
• Random planar maps and graphs with minimum degree two and three
• Generating labeled planar graphs uniformly at random
• A linear algorithm for the random sampling from regular languages
• Concentration of maximum degree in random planar graphs
• Random-bit optimal uniform sampling for rooted planar trees with given sequence of degrees and applications
• Random sampling of large planar maps and convex polyhedra
• The maximum degree of random planar graphs
• An experimental study on generating planar graphs
• Scalable Uniform Graph Sampling by Local Computation
• A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings
• Properties of random graphs via Boltzmann samplers
• Random graphs from a weighted minor-closed class
• scientific article; zbMATH DE number 15335 (Why is no real title available?)
• Analytic combinatorics of chord and hyperchord diagrams with k crossings
• scientific article; zbMATH DE number 2038777 (Why is no real title available?)
• The Evolution of Random Graphs on Surfaces
• On the Complexity of Sampling Vertices Uniformly from a Graph
• Phase transitions in graphs on orientable surfaces
• A bijection for plane graphs and its applications
• On random sampling in uniform hypergraphs
• Uniform random sampling of simple branched coverings of the sphere by itself
• 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?)
• Degree distribution in random planar graphs
• Classes of graphs embeddable in order-dependent surfaces
• Algorithms and Computation
• Exact-Size Sampling of Enriched Trees in Linear Time
• Domain-independent dynamic programming
• Title not available (Why is no real title available?)
• Explore and repair graphs with black holes using mobile entities

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)