Uniform random sampling of planar graphs in linear time

DOI10.1002/rsa.20275zbMath1201.05096arXiv0705.1287OpenAlexW3083123017MaRDI 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 graphsrandom generationBoltzmann sampling

Mathematics Subject Classification ID

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

Related Items (16)

Intruder alert! Optimization models for solving the mobile robot graph-clear problem ⋮ Classes of graphs embeddable in order-dependent surfaces ⋮ A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings ⋮ The maximum degree of random planar graphs ⋮ Concentration of maximum degree in random planar graphs ⋮ Explore and repair graphs with black holes using mobile entities ⋮ Random graphs from a weighted minor-closed class ⋮ Exact-Size Sampling of Enriched Trees in Linear Time ⋮ Analytic combinatorics of chord and hyperchord diagrams with \(k\) crossings ⋮ The evolution of random graphs on surfaces ⋮ A linear algorithm for the random sampling from regular languages ⋮ The Evolution of Random Graphs on Surfaces ⋮ Phase transitions in graphs on orientable surfaces ⋮ An Experimental Study on Generating Planar Graphs ⋮ Random planar maps and graphs with minimum degree two and three ⋮ Degree distribution in random planar graphs

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Uniform random sampling of planar graphs in linear time