Treewidth of graphs with balanced separations

Abstract

We prove that if every subgraph of a graph $G$ has a balanced separation of order at most $a$ then $G$ has treewidth at most $15a$. This establishes a linear dependence between the treewidth and the separation number.

Final version accepted for publication in J. Comb. Theory B