The pathwidth of a graph ,
also called the interval thickness, vertex separation number, and node searching
number, is one less than the size of the largest set in a path decomposition
.
Obstruction sets for pathwidth 1 and 2 were described in Kinnersley and Langston (1992) taking advantage of the fact that gate matrix layout with parameter is identical to the pathwidth problem with parameter
(Fellows and Langston 1989, Kinnersley
and Langston 1992).
pathwidth bound | obstruction |
110 forbidden minors |