Computer Science/Discrete Mathematics Seminar II

Planarity is a central theme in graph theory and combinatorial geometry, dating back to Euler. There are many beautiful characterizations of planar graphs such as Kuratowski's forbidden minor theorem and Koebe's circle packing theorem from the 1930s which naturally lead to studying generalizations of planarity. More recently, the separator theorem of Lipton and Tarjan for planar graphs has many applications, including fast algorithms on planar graphs for many fundamental problems which are NP-hard on general graphs. I will discuss a number of extensions of this result, including joint work with Janos Pach giving separator theorems for intersection graphs. Together with some surprising connections to partially ordered sets, these theorems lead to the solutions of several conjectures on graph drawings and intersection graphs.