Discrete Mathematics and Optimization Seminar
Monday, Nov. 1st, 2010
Tree-width and surface duality
Frederic Mazoit
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.' In this talk, I will present a generalisation of this statement. For every 2-cell embedding G in a surface of genus g, tw(G^*)<=tw(G)+1+g. I will also give examples of embedding matching this bound.