On minimizing width in linear layouts (Q751660)

The authors deal with finite undirected graphs with cutwidth 2 or 3. (Cutwidth cw is related to search number s and bandwidth B by: \(CW\leq \lfloor \deg (G)\rfloor \cdot B+1S\leq CW\leq \lfloor \deg (G)\rfloor \cdot (S-1)+1,\) where deg(G) denote the maximal degree of any vertex of G.) Interesting corollary: for \(\deg (G)=3\) the search number and cutwidth are identical. The author shows that these estimates are the best possible. Finally an algorithm operating for graphs with cutwidth 2 in linear time is presented.