Chordal embeddings of planar graph

Abstract : 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.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101804
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:06:43 AM
Last modification on : Wednesday, May 22, 2019 - 1:32:15 AM

File

RR2001-47.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101804, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

6

Files downloads

12