Chordal embeddings of planar graph
Résumé
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
Domaines
Informatique [cs]Origine | Fichiers produits par l'(les) auteur(s) |
---|