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.)