Aspects algorithmiques et combinatoires des réaliseurs des graphes plans maximaux

Abstract

Les réaliseurs, ou arbres de Schnyder, ont été introduits par Walter Schnyder à la fin des années 80 pour caractériser les graphes planaires, puis pour dessiner ces mêmes graphes sur des grilles (n-2)x(n-2). Dans ce document nous proposons dans un premier temps une extension du théorème de Wagner aux réaliseurs, qui nous permet d'établir une relation entre le nombre de feuilles et le nombre de faces tricolores d'un réaliseur. Ensuite, à l'aide d'une bijection entre les réaliseurs et les paires de chemins de Dyck qui ne se coupent pas, nous énumérons les réaliseurs. Un algorithme de génération aléatoire de p chemins de Dyck ne se coupant pas, est également présenté. Il permet en outre de générer aléatoirement des réaliseurs en temps linéaire. Puis nous montrons que grâce aux réaliseurs, il est possible de dessiner, à l'aide de lignes brisées des graphes planaires sur des grilles de largeur et de surface optimales. Enfin, nous proposons une généralisation des réaliseurs minimaux aux graphes planaires connexes : les arbres recouvrants bien-ordonnés. Grâce à cette généralisation ainsi qu'à une méthode de triangulation adaptée nous proposons un algorithme de codage des graphes planaires à n sommets en 5,007n bits.