# Geometric Separators and Their Applications

## Mark de Berg, Eindhoven University of Technology

## Date and time: 2pm (New York time), Tuesday, November 16, 2021

## Place: On Zoom (details provided on the seminar mailing list)

The famous Planar Separator Theorem states that any planar graph
$G=(V,E)$ with $n$ nodes admits a balanced separator of size $O(\sqrt{n})$,
that is, a subset $S \subset V$ that consists of $O(\sqrt{n})$ nodes
whose removal decomposes G into connected components of size at most
$2n/3$. The theorem was first proved in 1979 by Lipton and Tarjan, and
it has been instrumental in the design of algorithms for planar
graphs: it has been used to design efficient divide-and-conquer
algorithms, to design sub-exponential algorithms for various NP-hard
graph problems, and to design approximation algorithms for such
problems. In this talk I will discuss extensions of this theorem to
various classes of geometric intersection graphs. (A geometric
intersection graph is a graph whose nodes correspond to objects in the
plane, and for which there is an edge between two nodes if the
corresponding objects intersect.)