Tree-width of hypergraphs and surface duality
classification
💻 cs.DM
keywords
tree-widthgraphhypergraphsprovetheyapproximatelyboundconvinced
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.