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 .
As summarized in the table below, obstruction sets for pathwidth (consisting of the triangle graph and spoke graph , illustrated above) and (consisting of 110 graphs) 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 |
triangle graph and spoke graph | |
110 forbidden minors |
The set of 110 forbidden minors (Kinnersley and Langston 1992) is illustrated above. They are implemented in the Wolfram Language as GraphData["PathwidthForbidden"].