Conference Program


 (Add to Calendar)  Tuesday, August 21, 09:00 – 09:50 h, H0105:

Robin Thomas: A new look at excluding a non-planar graph

Chair: Gérard Cornuéjols


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 far-reaching 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 tree-decomposition into pieces, each of which has a k-near embedding in a surface S that does not embed H. Here a k-near embedding means that after deleting at most k vertices the graph can be drawn in S without crossings, except for k local areas of non-planarity, 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 Ken-ichi 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.

  There are three major facts that should be watched out for in all payday loans in the United States. One of the main advantages of Sovaldi is that it can be used by patients belonging to all 4 genotypes. Buy Sovaldi is a very strong drug, and as all of them, it has a number of side effects that can be caused.