of vertices the removal of which leaves a forest that can be partitioned into two smaller subforests with at most vertices each. A linear arrangement formed by recursively partitioning each of these two subforests, placing the separating vertices between them, has logarithmic vertex searching number. The same technique, applied to a tree-decomposition of a graph, shows that, if the treewidth of an -vertex graph is , then the pathwidth of is . Since outerplanar graphs, series–parallel graphs, and Halin graphs all have bounded treewidth, they all also have at most logarithmic pathwidth. As well as its relations to treewidth, pathwidth is also related to clique-width and cutwidth, via line graphs; the line graph of a graph has a vertex for each edge of and two vertices in are adjacent when the corresponding two edges of share an endpoint. Any family of graphs has bounded pathwidth if and only if its line graphs have bounded linear clique-width, where linear clique-width replaces the disjoint union operation from clique-width with the operation of adjoining a single new vertex. If a connected graph with three or more vertices has maximum degree three, then its cutwidth equals the vertex separation number of its line graph. In any planar graph, the pathwidth is at most proportional to the square root of the number of vertices. One way to find a path-decomposition with this width is (similarly to the logarithmic-width path-decomposition of forests described above) to use the planar separator theorem to find a set of vertices the removal of which separates the graph into two subgraphs of at most vertices each, and concatenate recursively-constructed path decompositions for each of these two subgraphs. The same technique applies to any class of graphs for which a similar separator theorem holds. Since, like planar graphs, the graphs in any fixed minor-closed graph family have separators of size , it follows that the pathwidth of the graphs in any fixed minor-closed family is again . For some classes of planar graphs, the pathwidth of the graph and the pathwidth of its dual graph must be within a constant factor of each other: bounds of this form are known for biconnected outerplanar graphs and for polyhedral graphs. For 2-connected planar graphs, the pathwidth of the dual graph is less than the pathwidth of the line graph. It remains open whether the pathwidth of a planar graph and its dual are always