Résumé de

Structuration de graphes planaires.

(by Denis Lapoire)

Cette thèse étend la théorie des grammaires algébriques aux cartes (c'est à dire des représentations de graphes sur des surfaces). Nous définissons des algèbres de cartes possédant de bonnes propriétés vis à vis des notions de dualité, de graphe induit et de planarité. Ceci nous permet d'étudier les liens existant entre d'une part les grammaires de graphes et les grammaires de cartes et d'autre part les grammaires de graphes et les grammaires algébriques de mots. Une première conséquence est la résolution d'une conjecture de Robertson et Seymour: le dual d'un graphe planaire G a pour largeur arborescente au plus celle de G plus un. Une seconde conséquence est que tout langage algébrique se caractèrise comme le langage des mots lus aux "bords" d'un ensemble définissable en Logique Monadique du Second-Ordre de graphes planaires de largeurs arborescente bornées.