Separators for Planar Graphs that are Almost Trees

Linda Cai, Sariel Har-Peled, Simiao Ye

We prove that a connected planar graph with $n$ vertices and $n+\mu$ edges has a vertex separator of size $O(\sqrt{\mu }+1)$, and this separator can be computed in linear time.