Eric Fusy

Un algorithme linéaire de génération aléatoire de graphes planaires étiquetés

Nous présentons un nouvel algorithme de génération aléatoire de graphes
planaires étiquetés, de complexité linéaire. Cet algorithme exploite une
décomposition combinatoire bien connue des graphes planaires par degré
croissant de connectivité : un graphe planaire peut être vu comme un arbre
de décomposition dont les noeuds sont occupés par des composantes
planaires 3-connexes. En utilisant le puissant cadre des générateurs de
Boltzmann, il suffit donc de générer l'arbre de décomposition, puis pour
chaque noeud de l'arbre générer un graphe planaire 3-connexe. Cette
dernière tâche peut être realisée en temps linéaire grace à une récente
correspondance combinatoire entre graphes planaires 3-connexes et arbres
binaires.