## Laying Out Iterated Line Digraphs Using Queues
Hasunuma, Toru
(2004)
Full text not available from this repository. ## AbstractIn this paper, we study a layout problem of a digraph using queues. The queuenumber of a digraph is the minimum number of queues required for a queue layout of the digraph. We present upper and lower bounds on the queuenumber of an iterated line digraph L^{k}(G). of a digraph G. In particular, 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 result on the queuenumber of L^{k}(G), it is shown that for any fixed digraph G, L^{k}(G) has a three-dimensional drawing with O(n) volume, where n is the number of vertices in L^{k}(G). We also apply these results to particular families of iterated line digraphs such as de Bruijn digraphs, Kautz digraphs, butterfly digraphs, and wrapped butterfly digraphs.
Repository Staff Only: item control page References |