In
graph theory, a
path decomposition of a graph
G is, informally, a representation of
G as a "thickened"
path graph, and the
pathwidth of
G is a number that measures how much the path was thickened to form
G. More formally, a path-decomposition is a sequence of subsets of vertices of
G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as
interval thickness (one less than the
maximum clique size in an
interval supergraph of
G),
vertex separation number, or
node searching number.
