TR-175: Separation of Graphs of Bounded Genus

Abstract

In this paper we improve some separator theorems for graphs of bounded genus. Let G be an n vertex connected graph of orientable genus g and T be a spanning tree of G. Any simple cycle of G that contains exactly one edge not in T is called a T-cycle of G. First we show that, if G is a triangulation, there exist g+l T-cycles of G whose removal divides G into components of no more than (2/3 )n vertices each. This improves the best previous 2g+l bound. The tool used to obtain this result is a sparse weighted graph associated with the genus g imbedding of G. Next we prove that a set C called a separator
of no more than ✓ (6g+6)n vertices of G that divides G. into components of no more than (2/3 )n vertices each exists. This is an improvement over the best previous ✓ ( 12g +6 )n bound on the size of C. Similar results are derived for graphs imbedded on non-orientable surfaces. A lower bound on the size of the smallest separator for toroidal graphs is obtained.