Uniform random sampling of planar graphs in linear time
From MaRDI portal
Publication:3055787
DOI10.1002/rsa.20275zbMath1201.05096arXiv0705.1287OpenAlexW3083123017MaRDI QIDQ3055787
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
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
