Laying Out Iterated Line Digraphs Using Queues

Hasunuma, Toru (2004) Laying Out Iterated Line Digraphs Using Queues. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003 , pp. 202-213(Official URL:

Full text not available from this repository.


In 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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-24595-7_19
Classifications: G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.999 Others
G Algorithms and Complexity > G.999 Others
P Styles > P.060 3D

Actions (login required)

View Item View Item