Skip to Main content Skip to Navigation
Conference papers

Random Sampling of Large Planar Maps and Convex Polyhedra

Gilles Schaeffer 1
1 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We present a versatile almost uniform random generator for planar embeddings of graphs (usually called \emph{maps}). This simple pseudo-algorithm is linear on average and gives in a few seconds random maps with up to one million edges or vertices. The class of planar graphs that can be obtained includes graphs of convex polyhedra (or 3-connected planar graphs) and convex irreducible triangulations (or 4-connected maximal planar graphs). Our algorithm relies on a combinatorial approach. First, new simpler compact encodings are defined using canonical unlabelled covering trees. Second, a general \emph{extraction/rejection} pseudo-algorithm is defined for composed structures. If correctly \emph{tuned} (we provide the necessary analysis for maps), it applies efficiently to a much wider class of planar graphs than previously known methods.
Document type :
Conference papers
Complete list of metadata
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 8:40:11 AM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM


  • HAL Id : inria-00098904, version 1



Gilles Schaeffer. Random Sampling of Large Planar Maps and Convex Polyhedra. Proceedings of the 31th annual ACM Symposium on the Theory of Computing - STOC'99, 1999, Atlanta, Georgia, pp.760-769. ⟨inria-00098904⟩



Record views