令G是一個由點集合(表示為V(G)) 和邊集合(表示為E(G))組成的圖形。G的點序列\sigma是雙向映射(bijection)到{1,2,…,|V|}。對u, v屬於V，若\sigma(u) < \sigma(v)則我們寫為 u <_\sigma v。G的d-佇列佈局包含一個點序列\sigma和G的邊分配到d個佇列，使得同一佇列不會有兩個邊是套疊的（即兩個邊uv, xy 屬於 E且u <_\sigma x <_\sigma y <_\sigma v）。G的佇列數(queuenumber)，定義為qn(G)，是最小整數d使得G有一個d-佇列佈局。若qn(G) < d，則G是一個d-佇列圖。在1992年，Heath等人[22，26]首先提出這個問題，並且證明辨識d-佇列圖問題是NP-complete問題，即使是d = 1。因此，更進一步的研究朝向考慮給定某些特性來限制圖的佇列數。

特別的是，互連網路的佇列佈局已經有應用在DIOGENES法([42] Rosenberg所提出)到可試驗的容錯處理器陣列。在1992年，Heath和Rosenberg[26]首先發表：n維的超立方體(Hypercube)，簡稱為Q_n，至多使用n-1個佇列即可佈局。最近，Hasunuma和Hitora[21]發表：qn(Q_n) <= n-2 對n >= 5。在這篇論文中，我們針對佇列佈局問題來介紹一個分歧設限(branch-and-bound)演算法。接著，我們針對一些互連網路的圖形來研究這個問題，如：超立方體、不完全超立方體(incomplete hypercube)、k元n維立方體(n-dimensional k-ary cube)和n維環面網格圖(n-dimensional toroidal grid)。

在前面兩個互連網路，我們所關注的是超立方體和不完全超立方體。我們提供了建置架構，以建立一個2-佇列佈局在Q_4。因此，我們指出，qn(Q_n) <= n-2 對n = 4時也是成立的。我們看到Hasunuma和Hitora[21]的做法而得到一個靈感，我們提供了一個特定的5-佇列佈局在Q_8。因此，qn(Q_n) <= n-3對n >= 8，改進了已知的研究成果。我們總結先前的文章[21，26，40，41，51]和本篇論文的成果如下：

（1）qn(Q_n) = \lceil n/2 \rceil 若 n 屬於 {2,3,4,5,6,7}，
（2）\lceil n/2 \rceil <= qn(Q_n) <= n-3 若 n >= 8。

第三個互連網路，我們所關注的是k元n維立方體(簡稱Q^k_n)。特別的是，Q^2_n是布林n維立方體(boolean n-cube)或超立方體，而Q^3_n是三元n維立方體(ternary n-cube)。Heath等人[22]發表：三元n維立方體至多使用2n-2個佇列就可佈局。我們延伸了這個結果在Q^k_n對4 <= k <= 8。並獲得輕微的改進在qn(Q^k_n) <= 2n-3 對k=3 和 n >= 3。第四個互連網路，我們所關注的是n維環面網格圖（簡稱T_{k1,k2,…,kn}）。我們得到兩個主要結果如下：

（1）qn(T_{k1,k2}) = 2 對 k1 >= 3 且 k2 >= 3，
（2）qn(T_{k1,k2,…,kn}) <= 2n-2對 ki >=3 且 i=1,2,…,n。

Let G be a graph with vertex set V(G) and edge set E(G). A vertex ordering \sigma of G is a bijection from V to {1,2,...,|V|}. For u,v \in V , we write u <_\sigma v if \sigma(u) < \sigma(v). A d-queue layout of G consists of a vertex ordering \sigma of G and a partition of its edges into d queues such that no two edges in the same queue are nested (i.e., two edges uv, xy \in E with u <\sigma x <\sigma y <\sigma v). The queuenumber of a graph G, denoted by qn(G), is the minimum number d such that G has a d-queue layout. A graph G is a d-queue graph if qn(G) <= d. In 1992, Heath et al. [20, 24] first introduced this problem and proved that the problem of recognizing d-queue graphs is NP-complete even if d = 1. Thus, further investigations tended to consider bounds on the queuenumber of graphs with certain properties

In particular, queue layouts of interconnection networks have applications in the DIOGENES approach, proposed by Rosenberg [42], to testable fault-tolerant arrays of processors. In 1992, Heath and Rosenberg [24] first showed that the n-dimensional hypercube, abbreviated as Q_n, can be laid out using at most n - 1 queues. Recently, Hasunuma and Hirota [19] showed that qn(Q_n) <= n - 2 for all n >= 5. In this dissertation, we introduce a branch-and-bound algorithm for the queue layout problem. Then, we study the queue layout problem on some interconnection networks which are hypercubes, incomplete hypercubes, n-dimensional k-ary cubes and n-dimensional toroidal grid.

The first two interconnection networks that we are concerned with are hypercubes and incomplete hypercubes. We provide a construction scheme to establish a 2-queue layout of Q_4 through which we point out that qn(Q_n) <= n-2 is still hold for n = 4. Inspired by the idea of Hasunuma and Hirota for obtaining the bound in [19], we provide a particular 5-queue layout of Q_8. As a consequence, qn(Q_n) <= n - 3 for n > 8, which improves the previously known result for the case n > 8. We summarize the results of this dissertation with previous results in [19, 24, 37, 38, 48] as follows.
(1) qn(Q_n) = \lceil n/2 \rceil if n \in {2,3,4,5,6,7},
(2) \lceil n/2 \rceil <= qn(Q_n) <= n-3 if n >= 8.

The third interconnection network that we are concerned with is the n-dimensional k-ary cube (abbreviated as Q^k_n). In particular, the class of Q^2_n is called the boolean n-cubes or hypercubes and the class of Q^3_n is called the ternary n-cubes. Heath et al. [20] showed that an n-dimensional ternary cube can be laid out using at most 2n-2 queues. We subsequently extend the upper bound to Q^k_n for 4 <= k <= 8 and obtain a slight improvement that qn(Q^k_n) <= 2n - 3 if k = 3 and n > 3.
The fourth interconnection network that we are concerned with is the n-dimensional toroidal grid graph (abbreviated as T_{k1,k2,…,kn}) which form a super class of Q^k_n. We obtain two main results as follows:
(1) qn(T_{k1,k2}) = 2 for k1 >= 3 且 k2 >= 3,
(2) qn(T_{k1,k2,…,kn}) <= 2n-2 for ki >=3 且 i=1,2,…,n.

[1] S. N. Bhatt, F. R. K. Chung, F. T. Leighton, and A. L. Rosenberg, Scheduling tree-dags using FIFO queues: A control-memory tradeoff, Journal of Parallel and Distributed Computing 33 (1996) 55-68.
[2] K. Bolding and L. Snyder, Mesh and torus chaotic routing, Proc. MIT/Brown Conference on Advanced Research in VLSI, 1992.
[3] Shekhar Borkar, Robert Cohn, George Cox, Thomas Gross, H. T. Kung, Monica Lam, Margie Levine, Brian Moore, Wire Moore, Craig Peterson, Jim Susman, Jim Sutton, John Urbanski, and Jon Webb, Supporting systolic and memory communication in iWARP. Proc. 17th Annual International Symposium on Computer Architecture, Seattle, 70-81, 1990.
[4] B. Bose, B. Broeg, Y. Kwon, and Y. Ashir, Lee distance and topological properties of k-ary n-cubes, IEEE Transactions on Computers 44 (1995) 1021-1030.
[5] J. Carbonaro and F. Verhoorn. Cavallino, the teraflops router and NIC, Proc. Hot Interconnects Symposium IV, August 1996.
[6] W. J. Dally, Performance analysis of k-ary n-cube interconnection networks, IEEE Transactions on Computers 39 (1990) 775-785.
[7] K. Day and A. E. Al-Ayyoub, Fault diameter of k-ary n-cube networks, IEEE Transactions on Parallel and Distributed Systems 8 (1997) 903-907.
[8] V. Dujmovic, P. Morin, and D. R. Wood, Layout of graphs with bounded tree-width, SIAM Journal on Computing 34 (2005) 553-579.
[9] V. Dujmovic, and D. R. Wood, On linear layouts of graphs, Discrete Mathematics and Theoretical Computer Science 6 (2004) 339-358.
[10] V. Dujmovic, and D. R. Wood, Upward three-dimensional grid drawings of graphs, Order 23 (2006) 1-20.
[11] S. Even and A. Itai, Queues, stacks, and graphs, in: Proc. International Symposium on Theory of Machines and Computations, Zvi Kohavi and Azaria Paz (Eds.), 71-86, Academic Press, 1971.
[12] J. F. Fang, J. Y. Hsiao, C. Y. Tang, Embedding cycles and meshes onto incomplete hypercubes, International Journal of Computer Mathematics 75 (2000) 1-19.
[13] J. F. Fang and K. C. Lai, Embedding the incomplete hypercube in books, Information Processing Letters 96 (2005) 1-6.
[14] J. L. Ganley, Stack and queue layouts of Halin graphs, 1995, manuscript.
[15] E. D. Giacomo, G. Liotta, and H. Meijer, Computing straightline 3D grid drawings of graphs in linear volume, Computational Geometry 32 (2005) 26-58.
[16] E. D. Giacomo, G. Liotta, H. Meijer, and S. K. Wismath, Volume requirements of 3D upward drawings, Discrete Mathematics 309 (2009) 1824-1837.
[17] T. Hasunuma, Queue layouts of iterated line directed graphs, Discrete Applied Mathematics 155 (2007) 1141-1154.
[18] T. Hasunuma, Improved book-embeddings of incomplete hypercubes, Discrete Applied Mathematics 157 (2009) 1423-1431.
[19] T. Hasunuma and M. Hirota, An improved upper bound on the queuenumber of the hypercube, Information Processing Letters 104 (2007) 41-44.
[20] L. S. Heath, F. T. Leighton, and A. L. Rosenberg, Comparing queues and stacks as mechanisms for laying out graphs, SIAM Journal on Discrete Mathematics 5 (1992) 398-412.
[21] L. S. Heath and S. V. Pemmaraju, Stack and queue layouts of posets, SIAM Journal on Discrete Mathematics 10 (1997) 599-625.
[22] L. S. Heath and S. V. Pemmaraju, Stack and queue layouts of directed acyclic graphs: part II, SIAM Journal on Computing 28 (1999) 1588-1626.
[23] L. S. Heath, S. V. Pemmaraju, and A. N. Trenk, Stack and queue layouts of directed acyclic graphs: part I, SIAM Journal on Computing 28 (1999) 1510-1539.
[24] L. S. Heath and A. L. Rosenberg, Laying out graphs using queues, SIAM Journal on Computing 21 (1992) 927-958.
[25] T. Horie, H. Ishihata, and M. Ikesaka. Design and implementation of an interconnection network for the AP1000, Proc. Information Processing, IFIP '92, Madrid, 1992.
[26] M. S. Horng, D. J. Chen, and K. L. Ku, Parallel routing algorithm for incomplete hypercube interconnection networks, Parallel Computing 20 (1994) 1739-1761.
[27] E. Horowitz, S. Sanhni, and D. Mehta, Fundamentals of data structures in C, W. H. Freeman. 2007.
[28] S. H. Hu and H. L. Chen, An effcient routing algorithm in incomplete hypercubes, Parallel Computing 20 (1994) 1721-1738.
[29] A. Imamiya and A. Nozaki, Generating and sorting permutations using restricted-deques, Information Processing in Japan 17 (1977) 80-86.
[30] S. M. Johnson, Generation of permutations by adjacent transpositions, Mathematical Computing 17 (1963) 282-285.
[31] D. B. Johnson, A priority queue in which initialization and queue operations take O(log log D) time, Mathematical Systems Theory 15 (1982) 295-309.
[32] H. P. Katseff, Incomplete hypercubes, IEEE Transactions on Computers 37 (1988) 604-608.
[33] S. Konstantinidou and L. Snyder. The Chaos router, IEEE Transactions on Computers 43 (1994) 1386-1397.
[34] F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, CA, 1992.
[35] W. Oed. The Cray research massively parallel processor system, CRAY T3D. Cray Research, Munich, 1993.
[36] E. T. Ordman and W. Schmitt, Permutations using stacks and queues, in Proc. 24th Southeastern International Conference on Combinatorics, Graph Theory, and Computing 96 (1993) 57-64.
[37] K. J. Pai, J. M. Chang, and Y. L. Wang, A note on "An improved upper bound on the queuenumber of the hypercube", Information Processing Letters 108 (2008) 107-109.
[38] K. J. Pai, J. M. Chang, and Y. L. Wang, A new upper bound on the of the hypercube, Discrete Mathematics , to appear. (doi:10.1016/j.disc.2009.09.007)
[39] S. V. Pemmaraju, Exploring the Powers of Stacks and Queues via Graph Layouts, Ph.D. thesis, Virginia Polytechnic Institute and State University, U.S.A., 1992.
[40] V. R. Pratt, Computing permutations with double-ended queues, parallel stacks and parallel queues, in: Proc. 5th Annual ACM Symposium on Theory of Computing (STOC'73), 268-277, ACM, 1973.
[41] S. Rengarajan and C. E. Madhavan, Stack and queue number of 2-trees, in Proc. 1st Annual International Conf. on Computing and Combinatorics (COCOON'95), Ding-Zhu Du and Ming Li (Eds.), LNCS 959, 203-212, Springer, 1995.
[42] A. L. Rosenberg, The diogenes approach to testable fault-tolerant arrays of processors, IEEE Transactions on Computers 32 (1983) 902-910.
[43] S. L. Scott and G. Thorson. The Cray T3E network: adaptive routing in a high performance 3D torus, Proc. Hot Interconnects Symposium IV, August 1996.
[44] R. E. Tarjan, Sorting using networks of queues and stacks, Journal of the ACM 19 (1972) 341-346.
[45] H. F. Trotter, Algorithm 115, Communications of the ACM 5 (1962) 434-435.
[46] N. F. Tzeng and H. L. Chen, Structural and tree embedding aspects of incomplete hypercubes, IEEE Transactions on Computers 43 (1994) 1434-1439.
[47] D. R. Wood, Queue layouts, tree-width, and three-dimensional graph drawing, in: Proc. 22nd Foundations of Software Technology and Theoretical Computer Science (FSTTCS'02), M. Agrawal and A. Seth (Eds.), LNCS 2556, 348-359, Springer, 2002.
[48] D. R. Wood, Queue layouts of graph products and powers, Discrete Mathematics and Theoretical Computer Science 7 (2005) 255-268.