Optimal linear arrangement of a rectangular grid Original Research Article

An optimal linear arrangement of a finite simple graph G=(V,E) with vertex set V, edge set E, and |V|=N, is a map f from V onto {1,2,…,N} that minimizes ∑{u,v}∈E|f(u)−f(v)|. We determine optimal linear arrangements for m×n rectangular grids where V={1,2,…,m}×{1,2,…,n} and E={{(i,j),(k,ℓ)}: |i−k|+|j−ℓ|=1}. When m⩾n⩾5, they are disjoint from bandwidth-minimizing arrangements for which f minimizes the maximum |f(u)−f(v)| over E. The different solutions to the bandwidth and linear arrangement problems for rectangular grids is reminiscent of Harperʹs result (J. Soc. Ind. Appl. Math. 12 (1964) 131–135; J. Combin. Theory 1 (1966) 385–393) of different bandwidth and linear arrangement solutions for the hypercube graph with vertex set {0,1}n and edge set {{(x1,x2,…,xn), (y1,y2,…,yn)}: ∑i|xi−yi|=1}.