Track Drawings of Graphs with Constant Queue Number

Di Giacomo, Emilio and Meijer, Henk (2004) Track Drawings of Graphs with Constant Queue Number. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 214-225 (Official URL:

Full text not available from this repository.


A k-track drawing is a crossing-free 3D straight-line drawing of a graph G on a set of k parallel lines called tracks. The minimum value of k for which G admits a k-track drawing is called the track number of G. In [9] it is proved that every graph from a proper minor closed family has constant track number if and only if it has constant queue number. In this paper we study the track number of well-known families of graphs with small queue number. For these families we show upper bounds and lower bounds on the track number that significantly improve previous results in the literature. Linear time algorithms that compute track drawings of these graphs are also presented and their volume complexity is discussed.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-24595-7_20
Classifications:P Styles > P.720 Straight-line
G Algorithms and Complexity > G.999 Others
P Styles > P.060 3D
ID Code:451

Repository Staff Only: item control page


S. Cornelsen, T. Schank, and D. Wagner. Drawing graphs on two and three lines. In Proc. GD 2002, volume 2528 of LNCS, pages 31-41. Springer-Verlag, 2002.

V. Dujmovic, P. Morin, and D. Wood. Pathwidth and three-dimensional straight line grid drawings of graphs. In Proc. GD 2002, volume 2528 of LNCS, pages 42-53. Springer-Verlag, 2002.

V. Dujmovic and D. Wood. New results in graph layout. Technical Report TR-03-04, School of Computer Science, Carleton University, 2003.

V. Dujmovic and D. Wood. Tree-partitions of k-trees with application in graph layout. In Proc. WG 2003, LNCS. Springer-Verlag, to appear.

S. Felsner, G. Liotta, and S. Wismath. Straight line drawings on restricted integer grids in two and three dimensions. In Proc. GD 2001, volume 2265 of LNCS, pages 328-342. Springer-Verlag, 2001.

J. L. Ganley. Stack and queue layouts of Halin graphs. 1995, manuscript.

R. Halin. Studies in minimally connected graphs. 1995, manuscript.

R. Halin. Studies in minimally connected graphs. In Combinatorial Mathematics and its Applications, pages 129-136. New York, Academic Press, 1971.

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

D. Wood. Queue layouts, tree-width, and three-dimensional graph drawing. In Proc. FSTTCS 2002, volume 2556 of LNCS., pages 348-359. Springer-Verlag, 2002.