Chordal embeddings of planar graphs

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 this conjecture in the affirmative, using algebraic techniques. We give a much shorter proof of this result.

Data and Resources

Additional Info

Field Value
Source ISSN: 0012-365X
Author Bouchitté, Vincent, Mazoit, Frédéric, Todinca, Ioan
Maintainer CCSD
Last Updated May 10, 2026, 00:07 (UTC)
Created May 10, 2026, 00:07 (UTC)
Identifier hal-00085469
Language en
contributor Laboratoire de l'Informatique du Parallélisme (LIP) ; École normale supérieure de Lyon (ENS de Lyon) ; Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL) ; Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)
creator Bouchitté, Vincent
date 2003-05-10T00:00:00
harvest_object_id 36f359aa-08fb-4aac-a611-caff27c6b08b
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-10-13T00:00:00
set_spec type:ART