Paper Info
Title
Queue layouts of iterated line directed graphs
Abstract
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 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 L^k(G), it is shown that for any fixed directed graph G, L^k(G) has a three-dimensional drawing with O(n) volume, where n is the number of vertices in 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.
Year
DOI
Venue
2007
10.1016/j.dam.2006.04.045
Discrete Applied Mathematics
Keywords
Field
DocType
kautz directed graphs,butterfly directed graphs,de bruijn directed graphs,iterations k,minimum number,k queue,queue layout,iterated line directed graphs,k-ary butterfly,three-dimensional drawing,graph l,graph g,interconnection networks,iterated line,graph g.,directed graph,three dimensional,upper bound,linear order,upper and lower bounds
Discrete mathematics,Combinatorics,Path (graph theory),Line graph,Queue,Directed graph,Directed acyclic graph,De Bruijn sequence,Mathematics,Feedback arc set,Graph (abstract data type)
Journal
Volume
Issue
ISSN
155
9
Discrete Applied Mathematics
Citations 
PageRank 
References 
7
0.57
15
Authors
1
Name
Order
Citations
PageRank
Toru Hasunuma114216.00