Layout Volumes of the HypercubeTorok, Lubomir and Vrt'o, Imrich (2004) Layout Volumes of the Hypercube. In: Graph Drawing 12th International Symposium, GD 2004, September 29October 2, 2004 , pp. 414424(Official URL: http://dx.doi.org/10.1007/9783540318439_42). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540318439_42
AbstractWe study 3dimensional layouts of the hypercube in a 1active 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 Nvertex hypercubes. Especially, we have $ {\rm VOL}_{1AL}(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 1active layer layout can be easily extended to a 2active layer (bottom and top) layout which improves a result from [5]. This research was partially supported by the VEGA grant No. 2/3164/23.
Actions (login required)
