Star-Based Separators for Intersection Graphs of $c$-Colored Pseudo-Segments

M. de Berg, B. M. P. Jansen, J. S. K. Lamme

The Planar Separator Theorem, which states that any planar graph $\mathcal{G}$ has a separator consisting of $O(\sqrt{n})$ nodes whose removal partitions $\mathcal{G}$ into compone…