Stack and Queue Layouts for Toruses and Extended Hypercubes




Bettayeb, Said

Journal Title

Journal ISSN

Volume Title


Hawaii International Conference on System Sciences


Linear layouts play an important role in many applications including networks and VLSI design. Stack and queue layouts are two important types of linear layouts. We consider the stack number, s(G), and queue number, q(G), for multidimensional k-ary hypercubes and toruses. Heath, Leighton, and Rosenberg showed that d-dimensional ternary hypercubes have stack number ¿,(N 1/9 ), with N=3 d nodes. Malitz showed that E edges implies stack number O(¿E). For k-ary d-dimensional hypercubes, with N = k d vertices, Malitz's bound is O(k d/2 ). We improve this to 2 d+1 -3. The 2 d+1 -3 bound holds for arbitrary d-dimensional toruses. The queue number of d-dimensional k-ary hypercubes or toruses is bounded by O(d). Hence, Heath, Leighton, and Rosenberg exhibit an exponential tradeoff between s(G) and q(G) for multidimensional ternary hypercubes. Conversely, they conjectured that, for any G, q(G) is O(s(G)). We present a family {H} of modified multidimensional toruses and conjecture that q(H) is not O(s(H)).



Hypercubes, Multidimensional systems, Computer science, Upper bound, Lakes, Very large scale integration, Books, Application software, Routing, Parallel processing


Stack and Queue Layouts for Toruses and Extended Hypercubes (with Hussain Heydari, Linda Morales, Hal Sudborough), Proc. Of the Hawaii International Conference on System Sciences, Jan. 2010 (HICSS 10).