Algorithms and obstructions for linear-width and related search parameters (Q1582084): Difference between revisions

Define the width of a linear ordering \((e_1, \ldots, e_r)\) of the edges of a graph \(G=(V,E)\) to be the maximum, over all \(i\), of the number of vertices that are incident with edges from \(\{e_1, \ldots, e_i\}\), and are incident with edges from \(\{e_{i+1}, \ldots, e_r\}\). The linear-width of a graph is the minimum width over all orderings of its edges. If we take a minor of a graph, then the linear-width cannot increase. Thus, for each \(k\), the class of graphs of linear-width at most \(k\) is closed under taking of minors, and hence has, by the work of Robertson and Seymour, a finite characterization by its obstruction set. In this paper, the obstruction set for linear-width at most two is given: it contains exactly 57 graphs. Also, with help of a connection to the mixed search number, the paper identifies the set of acyclic forbidden minors in the obstruction set of linear-width at most \(k\), for any \(k\geq 1\); and linear time algorithms for checking linear-width, mixed search, or edge-search at most two are given; these also can construct the corresponding edge orderings or search strategies.