pith. sign in

arxiv: 1006.3167 · v2 · pith:DNLPF7D3new · submitted 2010-06-16 · 💻 cs.DM

Tree-width of hypergraphs and surface duality

classification 💻 cs.DM
keywords tree-widthgraphhypergraphsprovetheyapproximatelyboundconvinced
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.