Layout Volumes of the Hypercube

Torok, Lubomir and Vrt'o, Imrich (2004) Layout Volumes of the Hypercube. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004 , pp. 414-424(Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_42).

Full text not available from this repository.

Abstract

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 [5]. 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 $ {\rm VOL}_{1-AL}(Q_{\log N})= \frac{2}{3}N^{\frac{3}{2}}\log N +O(N^{\frac{3}{2}}), $ for even log N and ${\rm VOL}(Q_{\log N})=\frac{2\sqrt{6}}{9}N^{\frac{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 [5]. This research was partially supported by the VEGA grant No. 2/3164/23.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-31843-9_42
Classifications: A General Literature > A.001 Introductory and Survey
URI: http://gdea.informatik.uni-koeln.de/id/eprint/612

Actions (login required)

View Item View Item