Queue layouts of iterated line directed graphs
In this paper, we study queue layouts of iterated line directed graphs. A k-queue layout of a directed graph consists of a linear ordering of the vertices and an assignment of each arc to exactly one of the k queues so that any two arcs assigned to the same queue do not nest. The queuenumber of a directed graph is the minimum number of queues required for a queue layout of the directed graph. We present upper and lower bounds on the queuenumber of an iterated line directed graph Lk(G) L k ( G ) of a directed graph G. Our upper bound depends only on G and is independent of the number of iterations k . Queue layouts can be applied to three-dimensional drawings. From the results on the queuenumber of Lk(G) L k ( G ) , it is shown that for any fixed directed graph G , Lk(G) L k ( G ) has a three-dimensional drawing with O(n) O ( n ) volume, where n  is the number of vertices in Lk(G) L k ( G ) . These results are also applied to specific families of iterated line directed graphs such as de Bruijn, Kautz, butterfly, and wrapped butterfly directed graphs. In particular, the queuenumber of k-ary butterfly directed graphs is determined if k is odd.
queue layout iterated line directed graphs three-dimensional drawing butterfly directed graphs interconnection networks de bruijn directed graphs kautz directed graphs