20041201
Track layouts of graphs
Publication
Publication
Discrete Mathematics and Theoretical Computer Science , Volume 6  Issue 2 p. 497 522
A (k,t)track layout of a graph G consists of a (proper) vertex tcolouring of G, a total order of each vertex colour class, and a (nonproper) edge kcolouring such that between each pair of colour classes no two monochromatic edges cross. This structure has recently arisen in the study of threedimensional graph drawings. This paper presents the beginnings of a theory of track layouts. First we determine the maximum number of edges in a (k,t)track layout, and show how to colour the edges given fixed linear orderings of the vertex colour classes. We then describe methods for the manipulation of track layouts. For example, we show how to decrease the number of edge colours in a track layout at the expense of increasing the number of tracks, and vice versa. We then study the relationship between track layouts and other models of graph layout, namely stack and queue layouts, and geometric thickness. One of our principle results is that the queuenumber and tracknumber of a graph are tied, in the sense that one is bounded by a function of the other. As corollaries we prove that acyclic chromatic number is bounded by both queuenumber and stacknumber. Finally we consider track layouts of planar graphs. While it is an open problem whether planar graphs have bounded tracknumber, we prove bounds on the tracknumber of outerplanar graphs, and give the best known lower bound on the tracknumber of planar graphs.
Additional Metadata  

, , , , , , , , , , , , ,  
Discrete Mathematics and Theoretical Computer Science  
Organisation  School of Linguistics and Language Studies 
Dujmović, V, Pór, A. (Attila), & Wood, D. (2004). Track layouts of graphs. Discrete Mathematics and Theoretical Computer Science, 6(2), 497–522.
