Tree-width of hypergraphs and surface duality

F Mazoit - Journal of Combinatorial Theory, Series B, 2012 - Elsevier
Journal of Combinatorial Theory, Series B, 2012Elsevier
In Graph minors III, Robertson and Seymour write:“It seems that the tree-width of a planar
graph and the tree-width of its geometric dual are approximately equal—indeed, we have
convinced ourselves that they differ by at most one.” They never gave a proof of this. In this
paper, we prove a generalisation of this statement to embedding of hypergraphs on general
surfaces, and we prove that our bound is tight.
In Graph minors III, Robertson and Seymour write: “It seems that the tree-width of a planar graph and the tree-width of its geometric dual are approximately equal — indeed, we have convinced ourselves that they differ by at most one.” They never gave a proof of this. In this paper, we prove a generalisation of this statement to embedding of hypergraphs on general surfaces, and we prove that our bound is tight.
Elsevier