Graphs and Matroids Seminar - Rose McCarty

Thursday, October 24, 2019 4:00 pm - 4:00 pm EDT (GMT -04:00)

Title: Sublinear separators in intersection graphs of convex shapes

Speaker: Rose McCarty
Affiliation: University of Waterloo
Room: MC 5501


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.