Optimal linear arrangement of a rectangular grid

An optimal linear arrangement of a finite simple graph G =(V,E) with vertex set V, edge set E, and textbackslash{}Vtextbackslash{} = N, is a map f from V onto {1,2,...,N}- that minimizes Sigma({u,v}is an element of E) textbackslash{}f(u)- f(v)textbackslash{} We determine optimal linear arrangements for m x n rectangular grids where V =(1,2,...,m)x {1,2,..., n} and E = {{(i,j), (k, l)}: textbackslash{}i - ktextbackslash{} + textbackslash{}j - ltextbackslash{} = 1}. When m greater than or equal to n greater than or equal to 5, they are disjoint from bandwidth-minimizing arrangements for which f minimizes the maximum If(u)- f(v)l over E. The different solutions to the bandwidth and linear arrangement problems for rectangular grids is reminiscent of Harper's result (J. Sec. 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 {{(x(1),x(2),...,x(n)), (y(1),y(2),..., y(n))}: Sigma(i) textbackslash{}x(i) - y(i)textbackslash{} = 1} (C) 2000 Elsevier Science B.V. All rights reserved.