Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
Lyudmil Aleksandrov, Hristo N. Djidjev · SIAM Journal on Discrete Mathematics · 1996
This paper develops new techniques for constructing separators for graphs embedded on surfaces of bounded genus. For any arbitrarily small positive $\varepsilon $ we show that any n-vertex graph G of genus g can be divided in $O(n + g)$ time into components whose sizes do not exceed $\varepsilon n$ by removing a set C of $O(\sqrt {(g + 1/\varepsilon )} n)$ vertices. Our result improves the best previous ones with respect to the size of C and the time complexity of the algorithm. Moreover, we show that one can cut off from G a piece of no more than $(1 - \varepsilon )n$ vertices by removing a set of $O(\sqrt {n\varepsilon (g\varepsilon + 1)} )$ vertices. Both results are optimal up to a constant factor.