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

Random graphs from a weighted minor-closed class, Analytic combinatorics of chord and hyperchord diagrams with \(k\) crossings, Degree distribution in random planar graphs, 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