2010/06/16 by Frédéric Mazoit, Mazoit, Frédéric · 1 citation
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM
paper · pdf · doi:10.48550/arxiv.1006.3167
arxiv created 2011/12/01 · arxiv updated 2011/12/02
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.