interval graphs Cutwidth, the minimum possible width of a linear ordering of the vertices of a graph Tree-depth, a number that is bounded for a minor-closed graph family if and only if the family excludes a path Degeneracy, a measure of the sparsity of a graph that is at most equal to its path width Graph bandwidth, a different NP-complete optimization problem involving linear layouts of graphs Strahler number, a measure of the complexity of rooted trees defined similarly to pathwidth of unrooted trees Notes References . . . . . . . . . . . . . . . . . . . . . . . . . . . As cited by . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Graph minor theory Graph invariants