The congestion of n-cube layout on a rectangular grid

AbstractWe consider the problem of embedding the n-dimensional cube into a rectangular grid with 2n 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