The congestion of n -cube layout on a rectangular grid

Abstract We consider the problem of embedding the n -dimensional cube into a rectangular grid with 2 n vertices in such a way as to minimize the congestion, the maximum number of edges along any point of the grid. After presenting a short solution for the cutwidth problem of the n -cube (in which the n -cube is embedded into a path), we show how to extend the results to give an exact solution for the congestion problem.