Two models of two-dimensional bandwidth problems

The two-dimensional bandwidth problem is to embed a graph G into an n×n grid in the plane such that the maximum distance between adjacent vertices is as small as possible. Here, the “distance” has two different meanings: the L1-norm distance and L∞-norm distance. So we have two models of two-dimensional bandwidth problem. This paper investigates the basic properties and relations of these two models. Some lower bounds, upper bounds, and exact results are presented.