Geodesic
A Direct Decomposition of 3-Connected Planar Graphs
Séminaire lotharingien de combinatoire, 54A (2005-2007)

Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website

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. 

@article{SLC_2005-2007_54A_a10,
     author = {Manuel Bodirsky and Clemens Gr\"opl and Daniel Johannsen and Mihyun Kang},
     title = {A {Direct} {Decomposition} of {3-Connected} {Planar} {Graphs}},
     journal = {S\'eminaire lotharingien de combinatoire},
     publisher = {mathdoc},
     volume = {54A},
     year = {2005-2007},
     url = {http://geodesic.mathdoc.fr/item/SLC_2005-2007_54A_a10/}
}
TY  - JOUR
AU  - Manuel Bodirsky
AU  - Clemens Gröpl
AU  - Daniel Johannsen
AU  - Mihyun Kang
TI  - A Direct Decomposition of 3-Connected Planar Graphs
JO  - Séminaire lotharingien de combinatoire
PY  - 2005-2007
VL  - 54A
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SLC_2005-2007_54A_a10/
ID  - SLC_2005-2007_54A_a10
ER  - 
%0 Journal Article
%A Manuel Bodirsky
%A Clemens Gröpl
%A Daniel Johannsen
%A Mihyun Kang
%T A Direct Decomposition of 3-Connected Planar Graphs
%J Séminaire lotharingien de combinatoire
%D 2005-2007
%V 54A
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SLC_2005-2007_54A_a10/
%F SLC_2005-2007_54A_a10
Manuel Bodirsky; Clemens Gröpl; Daniel Johannsen; Mihyun Kang. A Direct Decomposition of 3-Connected Planar Graphs. Séminaire lotharingien de combinatoire, 54A (2005-2007). http://geodesic.mathdoc.fr/item/SLC_2005-2007_54A_a10/