Linear layouts measuring neighbourhoods in graphs

In this paper we introduce the graph layout parameter neighbourhood-width as a variation of the well-known cut-width. The cut-width of a graph G=(V,E)G=(V,E) is the smallest integer k  , such that there is a linear layout ϕ:V→{1,…,|V|}ϕ:V→{1,…,|V|}, such that for every 1⩽i<|V|1⩽i<|V| there are at most k   edges {u,v}{u,v} with ϕ(u)⩽iϕ(u)⩽i and ϕ(v)>iϕ(v)>i. The neighbourhood-width of a graph is the smallest integer k  , such that there is a linear layout ϕϕ, such that for every 1⩽i<|V|1⩽i<|V| the vertices u   with ϕ(u)⩽iϕ(u)⩽i can be divided into at most k   subsets each members having the same neighbourhood with respect to the vertices vv with ϕ(v)>iϕ(v)>i.We show that the neighbourhood-width of a graph differs from its linear clique-width or linear NLC-width at most by one. This relation is used to show that the minimization problem for neighbourhood-width is NP-complete.Furthermore, we prove that simple modifications of neighbourhood-width imply equivalent layout characterizations for linear clique-width and linear NLC-width.We also show that every graph of path-width k or cut-width k   has neighbourhood-width at most k+2k+2 and we give several conditions such that graphs of bounded neighbourhood-width have bounded path-width or bounded cut-width.