Graphs and Matroids Seminar - Rose McCarty

Title: Sublinear separators in intersection graphs of convex shapes

Abstract: 

A balanced separator of an n-vertex graph is set of vertices whose deletion leaves only components of size at most 2n/3. We give a new sufficient condition for an intersection graph of compact, convex sets in R^d to have a balanced separator of sublinear size. We discuss connections with previously known conditions and open problems on how to represent arbitrary classes of graphs with sublinear separators.

This is joint work with Zdeněk Dvořák and Sergey Norin.