HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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

https://hal.inria.fr/inria-00098904
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 8:40:11 AM
Last modification on : Friday, February 4, 2022 - 3:31:27 AM

Identifiers

  • HAL Id : inria-00098904, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

63