Cutwidth of triangular grids

When the vertices of an n -vertex graph G are numbered by the integers 1 through n , the length of an edge is the difference between the numbers on its endpoints. Two edges overlap if the larger of their lower numbers is less than the smaller of their upper numbers. The bandwidth of G is the minimum, over all numberings, of the maximum length of an edge. The cutwidth of G is the minimum, over all numberings, of the maximum number of pairwise overlapping edges. The bandwidth of triangular grids was determined by Hochberg, McDiarmid, and Saks in 1995. We show that the cutwidth of the triangular grid with side-length l is 2 l .