Abstract of

Structuration of planar graphs.

(by Denis Lapoire)

This thesis extends the algebraic approach to maps, which represent graphs on a surface. We define map grammars having good properties with respect to the notions of duality, induced-graph and planarity. This allows us to study the links between graph grammars and map grammars and the links between graph grammars and word grammars. As a first consequence, we prove a conjecture of Robertson and Seymour: the dual of some planar graph $G$ has a tree-width at most equal to the treewidth of $G$. As a second consequence, we prove that every context-free language of words can be characterized as the language of words readen at the "borders" of a MSO-definable set of planar graphs of bounded treewidth.