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, Perugia, Italy , pp. 202-213 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_19).

Full text not available from this repository.

Abstract

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
ID Code:450

Repository Staff Only: item control page

References

N. Alon, C. McDiarmid, and B. Reed, Acyclic coloring of graphs, Random Structures &Algorithms 2 (1991) 277-288.

J.-C. Bermond, E. Darrot, O. Delmas, and S. Perennes, Hamiltonian circuits in the directed wrapped butterfly network, Discrete Applied Math. 84 (1998), 21-42.

J.-C. Bermond and C. Peyrat, "De Bruijn and Kautz networks: A competition for the hypercube?," Hypercube and distributed computers, F. André, J.P. Verjus (Editors), North Holland, Amsterdam, 1989, pp. 279-293.

F. Bernhart and P.C. Kainen, The book thickness of a graph, J. Combin. Theory Ser. B 27 (1979), 320-331.

F.R.K. Chung, F.T. Leighton, and A.L. Rosenberg, Embedding graphs in books: a layout problem with application to VLSI design, SIAM J. Algebraic Discrete Methods 8 (1987), 33-58.

V. Dujmovic and D.R. Wood, Tree-Partitions of k-trees with applications in graph layouts, Proc. of WG'03, Lecture Notes in Comput. Sci., Springer, to appear.

V. Dujmovic and D.R. Wood, New results in graph layout, Tech. Report TR-2003-04, School of Computer Science, Carleton University, Canada, 2002.

V. Dujmovic, P. Morin, and D.R. Wood, Path-width and three-dimensional straight-line grid drawings of graphs, Proc. of GD'02, Lecture Notes in Comput. Sci. 2528, pp. 42-53, Springer, 2002.

S. Even and A. Itai, "Queues, stacks and graphs," Theory of Machines and Computations, Z. Kohavi and A. Paz (Editors), Academic Press, New York, 1971, pp. 71-86.

G. Fertin, A. Raspaud, and B. Reed, On star coloring of graphs, Proc. of WG'01, Lecture Notes in Comput. Sci. 2204, pp. 140-153, Springer, 2001.

M.A. Fiol, J.L.A. Yebra, and I. Alegre, Line digraph iterations and the (d,k) digraph problem, IEEE Trans. Comput. 33 (1984) 400-403.

R.A. Games, Optimal book embeddings of the FFT, Benes, and barrel shifter networks, Algorithmica 1 (1986), 233-250.

J.L. Ganley and L.S. Heath, The pagenumber of k-trees is O(k), Discrete Applied Math. 109 (2001), 215-221.

T. Hasunuma, Embedding iterated line digraphs in books, Networks 40 (2002) 51-62.

T. Hasunuma, Queuenumbers and stacknumbers of generalized de Brujin and Kautz digraphs, submitted.

T. Hasunuma and Y. Shibata, Embedding de Bruijn, Kautz and shuffle-exchange networks in books, Discrete Applied Math. 78 (1997), 103-116.

T. Hasunuma and Y. Shibata, Containment of butterflies in networks constructed by the line digraph operation, Inform. Process. Lett. 61 (1997), 25-30.

L.S. Heath, F.T. Leighton, and A.L. Rosenberg, Comparing queues and stacks as mechanisms for laying out graphs, SIAM J. Discrete Math. 5 (1992).

L.S. Heath, S.V. Pemmaraju, and A.N. Trenk, Stack and queue layouts of directed acyclic graphs I, SIAM J. Comput.28 (1999) 1510-1539.

L.S. Heath and S.V. Pemmaraju,Stack and queue layouts of directed acyclic graphs II, SIAM J. Comput.28 (1999) 1588-1626.

L.S. Heath and A.L. Rosenberg, Laying out graphs using queues, SIAM J. Comput. 21 (1992) 927-958.

M. Kronoe, K. Hagiwara, and N. Tokura, On the pagenumber of hypercubes and cube-connected cycles, IEICE Trans. J71-D (1988), 490-500 (in Japanese).

S.M. Malitz, Genus g graphs have pagenumbers 0(\sqrt{g}), J. Algorithms 17 (1994), 85-109.

D.J. Muder, M.L. Weaver, and D.B. West, Pagenumber of complete bipartite graphs, J. Graph Theory 12 (1988), 469-489.

S.V. Pemmaraju, Exploring the powers of stacks and queues via graph layouts, Ph.D thesis, Virginia Polytechnic Institute and State University, Virginia, USA, 1992.

S. Rengarajan and C.E. Veni Madhavan, Stack and queue number of 2-trees, Proc. of COCOON 95, Lecture Notes in Comput. Sci. 959, pp.203-212, Springer, 1995.

A.L. Rosenberg, The Diogenes approach to estable fault-tolerant arrays of processors, IEEE Trans. Comput. C-32 (1983), 902-910.

R.P. Swaminathan, D. Giriaj, and D.K. Bhatia, The pagenumber of the class of bandwidth-k graphs is k - 1, Inform. Process. Lett. 55 (1995), 71-74.

R.E. Tarjan, Sorting using networks of queues and stacks, J. Assoc. Comput. Mach., 19 (1972) 341-346.

D.R. Wood, Bounded degree book embeddings and three-dimensional orthogonal graph drawing, Proc. of GD'01, Lecture Notes in Comput. Sci. 2265, pp. 312-327, Springer, 2002.

D.R. Wood, Queue layouts, tree-width, and three-dimensional graph drawing, Proc. of FSTTCS '02, Lecture Notes in Comput. Sci. 2556, pp. 348-359, Springer, 2002.

M. Yannakakis, Embedding planar graphs in four pages, J. Comput. System Sci. 38 (1989), 36-67.