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 , pp. 214-225(Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_20).

Full text not available from this repository.

Abstract

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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/451

Actions (login required)

View Item View Item