Graph parameters measuring neighbourhoods in graphs—Bounds and applications

The neighbourhood-width of a graph G=(V,E)G=(V,E) is introduced in [F. Gurski, Linear layouts measuring neighbourhoods in graphs, Discrete Math. 306 (15) (2006) 1637–1650.] as 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| the vertices uu with ϕ(u)⩽iϕ(u)⩽i can be divided into at most k   subsets each members having the same neighbours with respect to the vertices vv with ϕ(v)>iϕ(v)>i.In this paper we show first bounds for the neighbourhood-width of general graphs, caterpillars, trees and grid graphs and give applications of the layout parameter neighbourhood-width in graph drawing and VLSI design.