papers in Robertson and Seymour's graph minor series, a path-decomposition is a tree decomposition in which the underlying tree of the decomposition is a path graph. The width of a path-decomposition is defined in the same way as for tree-decompositions, as , and the pathwidth of is the minimum width of any path-decomposition of . The subtraction of one from the size of in this definition makes little difference in most applications of pathwidth, but is used to make the pathwidth of a path graph be equal to one. Alternative characterizations As describes, pathwidth can be characterized in many equivalent ways. Gluing sequences A path decomposition can be described as a sequence of graphs that are glued together by identifying pairs of vertices from consecutive graphs in the sequence, such that the result of performing all of these gluings is . The graphs may be taken as the induced subgraphs of the sets in the first definition of path decompositions, with two vertices in successive induced subgraphs being glued together when they are induced by the same vertex in , and in the other direction one may recover the sets as the vertex sets of the graphs . The width of the path decomposition is then one less than the maximum number of vertices in one of the graphs . Interval thickness The pathwidth of any graph is equal to one less than the smallest clique number of an interval graph that contains as a subgraph. That is, for every path decomposition of one can find an interval supergraph of , and for every interval supergraph of one can find a path decomposition of , such that the width of the decomposition is one less than the clique number of the interval graph. In one direction, suppose a path decomposition of is given. Then one may represent the nodes of the decomposition as points on a line (in path order) and represent each vertex as a closed interval having these points as endpoints. In this way, the path decomposition nodes containing correspond to the representative points in the interval for . The intersection graph of the intervals formed from the vertices of is an interval graph that contains as a subgraph. Its maximal cliques are given by the sets of intervals containing the representative points, and its maximum clique size is one plus the pathwidth of . In the other