L'objet de ce stage sera
l'étude combinatoire et algorithmique d'une certaine classe de
propriétés caractérisant la notion de
planarité des graphes : ces propriétés ont eu dans
les deux dernières décennies des fortes
répercussions et applications dans plusieurs domaines, telles
que le dessin et le codage, l'énumération et la
génération aléatoire et exhaustive, ainsi que la
conception de structures de données é caces en
géométrie algorithmique. Les propriétés
combinatoires des graphes planaires dont on s'occupera sont connues
sous le nom de forêts de Schnyder ou réaliseurs : elles
peuvent s'exprimer en termes de d'orientations d'arêtes et
décompositions de graphes en arbres recouvrants. En particulier,
dans ce stage il s'agira d'approfondir la généralisation
de ces propriétés au cas, encore presque
inexploré, des cartes plongées sur des surfaces de genre
g fi xé.
|
|
Exemple de forêt de
Schnyder pour une triangulation planaire T. A gauche un ordre
canonique de T.
|
Une forêt de Schnyder pour
une triangulation de genre 1 (sur le tore)
|