|
|
Discrete Mathematics and Optimization Seminar
|
Monday, Nov. 1st, 2010
|
Tree-width and surface duality
Frederic Mazoit
LaBRI
|
|
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.
|
|
|
|