Chordal embeddings of planar graph

Vincent Bouchitté (1) , Frédéric Mazoit (1) , Ioan Todinca (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

Robertson and Seymour conjectured that the treewidth of a planar graph and the treewidth of its geometric dual differ by at most one. Lapoire solved the conjecture in the affirmative, using algebraic techniques. We give here a much shorter proof of this result.

Robertson et Seymour ont conjecturé que la largeur arborescente d'un graphe planaire et celle de son dual différent d'au plus un. Lapoire a prouvé cette conjecture en utilisant des outils algébriques. Nous donnons ici une preuve beaucoup plus courte de ce résultat

Mots clés: Duality; Planar Graphs; Treewidth

Mots clés: Graphes planaires; Largeur arborescente; Dualité

Domaines: Informatique [cs]

Vincent Bouchitté, Frédéric Mazoit, Ioan Todinca. Chordal embeddings of planar graph. [Research Report] Laboratoire de l'informatique du parallélisme. 2001, 2+14p. ⟨hal-02101804⟩