DIMACS Graduate Student Combinatorics Seminar Series

Title: Excluded Minor Theory

Speaker: Trevor Bass, Rutgers University

Date: Monday, November 17, 2003, 1:10 pm

Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ


We'll present the graph minor theorem and its most celebrated corollary, the excluded minor theorem, and we'll sketch a recent proof of the excluded minor theorem due to Thomassen. Then we'll give a sketch of an algorithm of Mohar that for each fixed surface decides whether a graph is embeddable in it in linear time. I promise that this algorithm is interesting because of its graph theoretic content, not because of its implications in computer science.