The Congestion of n-Cube Layout on a Rectangular Grid

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. 1 Introduction Let G = (V; E) represent a graph with vertex set V and edge set E. We may think of G as representing the wiring diagram of an electronic circuit, with the vertices representing components and the edges representing wires connecting them. A (vertex) numbering of G is a function j : V 7! f1; 2; : : : ; jV jg; which is one-to-one (and therefore onto). A numbering may be thought of as an embedding of G into a linear chassis. The cutwidth of G, with respect to j, cw(G; j), is the maximum number of wires which pass any point on the linear chassis: cw(G; j) = max l ..