Séminaire Lotharingien de Combinatoire, B54Ak (2007), 15 pp.
Manuel Bodirsky, Clemens Gröpl, Daniel Johannsen and Mihyun Kang
A Direct Decomposition of 3-Connected Planar Graphs
Abstract.
We present a decomposition strategy for c-nets,
i.e., rooted 3-connected planar maps.
The decomposition yields an algebraic equation for the number
of c-nets with a given number of vertices and a given size of the
outer face.
The decomposition also leads to a deterministic and polynomial time
algorithm to sample c-nets uniformly at random.
Using rejection sampling, we can also sample isomorphism types
of convex polyhedra, i.e., 3-connected planar graphs, uniformly at random.
Résumé.
Nous proposons une stratégie de décomposition pour les cartes pointées
3-connexes (c-réseaux). Cette décomposition permet d'obtenir une
équation algébrique pour le nombre de c-réseaux suivant le nombre de
sommets et la taille de la face extèrieure. On en déduit un algorithme de
complexité en temps polynomiale pour le tirage aléatoire uniforme des
c-réseaux. En utilisant une méthode à rejet, nous obtenons aussi un
algorithme de tirage aléatoire uniforme pour les graphes planaires
3-connexes.
Received: January 3, 2006.
Accepted: October 1, 2006.
Final Version: January 17, 2007.
The following versions are available: