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.
Type de document :
Communication dans un congrès
Proceedings of the 31th annual ACM Symposium on the Theory of Computing - STOC'99, 1999, Atlanta, Georgia, ACM press, pp.760-769, 1999
Liste complète des métadonnées

https://hal.inria.fr/inria-00098904
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:40:11
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • 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, ACM press, pp.760-769, 1999. 〈inria-00098904〉

Partager

Métriques

Consultations de la notice

68