For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 Queue Layouts of Toroidal GridsKung-Jui PAI  Jou-Ming CHANG  Yue-Li WANG  Ro-Yu WU  Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A    No.6    pp.1180-1186Publication Date: 2014/06/01Online ISSN: 1745-1337 DOI: 10.1587/transfun.E97.A.1180Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)Category: Keyword: Queue layout,  Toroidal grids,  Cartesian product,  Arched leveled-planar graphs,  Full Text: PDF(1MB)>> Buy this Article Summary:  A queue layout of a graph G consists of a linear order of its vertices, and a partition of its edges into queues, such that no two edges in the same queue are nested. The queuenumber qn(G) is the minimum number of queues required in a queue layout of G. The Cartesian product of two graphs G1 = (V1,E1) and G2 = (V2,E2), denoted by G1 × G2, is the graph with {:v1 ∈ V1 and v2 ∈ V2} as its vertex set and an edge (,) belongs to G1×G2 if and only if either (u1,v1) ∈ E1 and u2 = v2 or (u2,v2) ∈ E2 and u1 = v1. Let Tk1,k2,...,kn denote the n-dimensional toroidal grid defined by the Cartesian product of n cycles with varied lengths, i.e., Tk1,k2,...,kn = Ck1 × Ck2 × … × Ckn, where Cki is a cycle of length ki ≥ 3. If k1 = k2 = … = kn = k, the graph is also called the k-ary n-cube and is denoted by Qnk. In this paper, we deal with queue layouts of toroidal grids and show the following bound: qn(Tk1,k2,...,kn) ≤ 2n-2 if n ≥ 2 and ki ≥ 3 for all i = 1,2,...,n. In particular, for n = 2 and k1,k2 ≥ 3, we acquire qn(Tk1,k2) = 2. Recently, Pai et al. (Inform. Process. Lett. 110 (2009) pp.50-56) showed that qn(Qnk) ≤ 2n-1 if n ≥1 and k ≥9. Thus, our result improves the bound of qn(Qnk) when n ≥2 and k ≥9.