
Discrete Mathematics and Optimization Seminar

Monday, Nov. 1st, 2010
Treewidth and surface duality
Frederic Mazoit
LaBRI

In Graph Minors III, Robertson and Seymour write:'It seems
that the treewidth of a planar graph and the treewidth 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 2cell embedding G in a
surface of genus g, tw(G^*)<=tw(G)+1+g. I will also give examples of
embedding matching this bound.



