Chordal embeddings of planar graph - LARA - Libre accès aux rapports scientifiques et techniques
Rapport (Rapport De Recherche) Année : 2001

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
Fichier principal
Vignette du fichier
RR2001-47.pdf (272.85 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02101804 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101804 , version 1

Citer

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⟩
19 Consultations
56 Téléchargements

Partager

More