Uniform random sampling of planar graphs in linear time

DOI10.1002/rsa.20275zbMath1201.05096arXiv0705.1287MaRDI QIDQ3055787

É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

planar graphs; random generation; Boltzmann sampling

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

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, Random graphs from a weighted minor-closed class, Analytic combinatorics of chord and hyperchord diagrams with \(k\) crossings, Degree distribution in random planar graphs, Explore and repair graphs with black holes using mobile entities, 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, A linear algorithm for the random sampling from regular languages, The maximum degree of random planar graphs, An Experimental Study on Generating Planar Graphs, A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The asymptotic enumeration of rooted convex polyhedra
• Optimal coding and sampling of triangulations
• Transversal structures on triangulations: A combinatorial study and straight-line drawings
• Counting labelled 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
• Random planar graphs
• Planar maps as labeled mobiles
• The number of labeled 2-connected planar graphs
• A bijection for triangulations of a polygon with interior points and multiple edges
• Generating labeled planar graphs uniformly at random
• Planar graphs, via well-orderly maps and trees
• Singularity Analysis of Generating Functions
• Finite Continuous Time Markov Chains
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• 2-Isomorphic Graphs
• Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling
• The enumeration of c-nets via quadrangulations
• A Census of Planar Maps