Queue Layouts of Toroidal Grids

Kung-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-1186
Publication Date: 2014/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.1180
Type 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,v2>:v1V1 and v2V2} as its vertex set and an edge (<u1,u2>,<v1,v2>) 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 ki3. 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 ki3 for all i = 1,2,...,n. In particular, for n = 2 and k1,k23, 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.