### Finding small simple cycle separators for 2-connected planar graphs

- Series
- Graph Theory Working Seminar
- Time
- Wednesday, November 7, 2018 - 16:30 for 1.5 hours (actually 80 minutes)
- Location
- Skiles 006
- Speaker
- Michael Wigal – 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.