## March 11, 2016:

#
Recent Results on Small Separators of Planar Graphs

##
Muhammad Jawaherul Alam

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