Conference Program

PLENARY AND SEMI-PLENARY TALKS

 (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


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 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.

  Payday Loans In North Carolina. In this section we give only a brief summary recommendation for admission of Canadian Levitra. Full information can be found in the instructions for receiving medications with vardenafil.