On balanced separators, treewidth, and cycle rank

摘要

We investigate relations between different width parameters of graphs, in particular balanced separator number, treewidth, and cycle rank. Our main result states that a graph with balanced separator number k has treewidth at least k but cycle rank at most k · (1 + log n/k), thus refining the previously known bounds, as stated by Robertson and Seymour (1986) and by Bodlaender et al. (1995). Furthermore, we show that the improved bounds are best possible.