Conference Program
PLENARY AND SEMIPLENARY TALKS
Tuesday, August 21, 09:00 – 09:50 h, H0105:
Robin Thomas: A new look at excluding a nonplanar graph
Chair: Gérard Cornuéjols
Abstract:
At the heart of the Graph Minors project of Robertson and Seymour lies a deep theorem saying that every graph G with no minor isomorphic to a fixed graph H has a certain structure. The structure can then be exploited to deduce farreaching consequences. The exact statement requires some explanation, but roughly it says that there exists an integer k depending on H only such that G has a treedecomposition into pieces, each of which has a knear embedding in a surface S that does not embed H. Here a knear embedding means that after deleting at most k vertices the graph can be drawn in S without crossings, except for k local areas of nonplanarity, where crossings are permitted, but the graph is constrained in a different way, again depending on the parameter k. I will explain the theorem and its applications, and then will discuss recent work: a much simpler proof and a variation on the theorem, which adds some restrictive assumptions, but is much easier to state and to apply. Part of this is joint with Kenichi Kawarabayashi and Paul Wollan, and part is joint with Sergey Norin.
Biographical sketch:
Robin Thomas received his Ph.D. from Charles University in Prague, formerly Czechoslovakia, now the Czech Republic. He has worked at the Georgia Institute of Technology since 1989. Currently he is Regents' Professor of Mathematics and Director of the multidisciplinary Ph.D. program in Algorithms, Combinatorics, and Optimization. In 1994 and 2009 he and his coauthors won the D. Ray Fulkerson prize in Discrete Mathematics.
