circle graphs. However, the pathwidth may be computed in linear time for trees and forests,. It may also be computed in polynomial time for graphs of bounded treewidth including series–parallel graphs, outerplanar graphs, and Halin graphs, as well as for split graphs, for the complements of chordal graphs, for permutation graphs, for cographs, for circular-arc graphs, for the comparability graphs of interval orders, and of course for interval graphs themselves, since in that case the pathwidth is just one less than the maximum number of intervals covering any point in an interval representation of the graph. Approximation algorithms It is NP-hard to approximate the pathwidth of a graph to within an additive constant. The best known approximation ratio of a polynomial time approximation algorithm for pathwidth is . For earlier approximation algorithms for pathwidth, see and . For approximations on restricted classes of graphs, see . Graph minors A minor of a graph is another graph formed from by contracting edges, removing edges, and removing vertices. Graph minors have a deep theory in which several important results involve pathwidth. Excluding a forest If a family of graphs is closed under taking minors (every minor of a member of is also in ), then by the Robertson–Seymour theorem can be characterized as the graphs that do not have any minor in , where is a finite set of forbidden minors. For instance, Wagner's theorem states that the planar graphs are the graphs that have neither the complete graph nor the complete bipartite graph as minors. In many cases, the properties of and the properties of are closely related, and the first such result of this type was by , and relates bounded pathwidth with the existence of a forest in the family of forbidden minors. Specifically, define a family of graphs to have bounded pathwidth if there exists a constant such that every graph in has pathwidth at most . Then, a minor-closed family has bounded pathwidth if and only if the set of forbidden minors for includes at least one forest. In one direction, this result is straightforward to prove: if does not include at least one forest, then the -minor-free graphs do not have bounded pathwidth. For, in this case, the -minor-free graphs include all forests, and in particular they include the perfect binary trees. But a perfect binary tree with levels has pathwidth , so in this case