Finding small simple cycle separators for 2-connected planar graphs

Graph Theory Working Seminar
Wednesday, November 7, 2018 - 4:30pm
1.5 hours (actually 80 minutes)
Skiles 006
Georgia Tech
For a graph on $n$ vertices, a vertex partition $A,B,C$ is a $f(n)$-vertex separator if $|C| \le f(n)$ and $|A|,|B| \le \frac{2}{3}n$ and $(A,B) = \emptyset$. A theorem from Gary Miller states for an embedded 2-connected planar graph with maximum face size $d$ there exists a simple cycle such that it is vertex separator of size at most $2\sqrt{dn}$. This has applications in divide and conquer algorithms.