Title: Sublinear separators in intersection graphs of convex shapes
|Affiliation:||University of Waterloo|
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.
200 University Avenue West
Waterloo, ON N2L 3G1