Abstract: Separators identify structure in a graph by splitting it into roughly equal parts with little mutual interference. Efficient algorithm for finding separators for a graph class often leads to efficient divide-and-conquer algorithms for different problems on the graph class. A separator theorem typically provides worst-case guarantees on the balance of the parts and on the size of their shared boundary. Separator theorems have been found for planar graphs, bounded-genus graphs, and minor-free graphs. For a triangulated planar graph with n vertices, it is known that there exists a cycle of size O(sqrt(n)) that splits the graph in roughly equal sizes. In this talk we discuss some recent results on small separators for planar graphs.
First we show a simple proof for the existence of a planar separator exploiting simple geometry, probability theory and the well-known circle-packing theorem on planar graphs. This result can be also extended to reprove the existence of separators in graphs with k-ply intersection representation of d-dimentional balls, and the k-nearest neighbor graphs on a set of d-dimensional points. Finally we also describe a recent algorithm to construct a cycle separator with sqrt(8m) edges for a planar graph containing m edges.
(This talk is based on two recent papers: one is an arxiv paper by Sariel Har-Peled, and the other is an ALENEX 2013 paper by Eli Fox-Epstein, Shay Mozes, Phitchaya Mangpo Phothilimthana, and Christian Sommer.)