In the “16th NP-completeness column” [1]} Johnson compiled a list of graph classes for which many NP-complete problems are polynomial or even linear-time solvable. Some examples from this list are: trees, partial \(k\) -trees, chordal graphs, series parallel graphs, split graphs and co-graphs. A common feature shared by many of these classes is that their members admit some form of recursive decomposition. The same holds for the graph classes described by measuring the size of a smallest structural decomposition (e.g. tree-width or clique-width). Algorithms on such classes can often proceed by dynamic programming, taking advantage of the recursive structure of the input [2]}, [3]}, [4]}, [5]}.
