Graph Classes with Few Minimal Separators. II. A Dichotomy

A class F of graphs is called tame if every graph in F on n vertices contains at most nO(1) minimal separators, quasi-tame if every graph in F on n vertices contains at most 2logO(1)(n) minimal separators, and feral if there exists a constant c > 1 so that F contains n-vertex graphs with at least cn minimal separators for arbitrarily large n. The classification of graph classes into (quasi-) tame or feral has numerous algorithmic consequences, and has recently received considerable attention.