Layout Volumes of the Hypercube

摘要

We study 3-dimensional layouts of the hypercube in a 1-active layer and a general model. The problem can be understood as a graph drawing problem in 3D space and was addressed at Graph Drawing 2003. For both models we prove general lower bounds which relate volumes of layouts to a graph parameter called cutwidth. Then we propose tight bounds on volumes of layouts of N-vertex hypercubes. Especially, we have VOL_(1-AL)(Q_(log N)) = 2/3 N~(3/2) log N + O(N~(3/2)), for even log N and VOL(Q_(log N)) = 26~(1/2)N~(3/2) + O(N~(4/3) log N), for log N divisible by 3. The 1-active layer layout can be easily extended to a 2-active layer (bottom and top) layout which improves a result from.