Chordal embeddings of planar graph

Vincent Bouchitté; Frédéric Mazoit; Ioan Todinca

Reports

Chordal embeddings of planar graph

Vincent Bouchitté ¹ Frédéric Mazoit ¹ Ioan Todinca ¹

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

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.

Keywords : Duality Planar Graphs Treewidth

Document type :

Reports

Domain :

Computer Science [cs]

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, November 20, 2019 - 3:14:33 AM

Chordal embeddings of planar graph

File

Identifiers

Collections

Citation

Export

Metrics

22

32

Chordal embeddings of planar graph

File

Identifiers

Collections

Citation

Export

Share

Metrics

22

32