Beyond Planarity

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Beyond Planarity
Speaker:Jacob Fox
Affiliation:Princeton University
Date:Tuesday, April 21
Time/Room:10:30am - 12:30pm/S-101

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.