Carleton University
Technical Report TR-03-04
June 2003
New Results in Graph Layout
Abstract
A track layout of a graph consists of a vertex colouring, an edge colouring, and a total or- der of each vertex colour class such that between each pair of vertex colour classes, there is no monochromatic pair of crossing edges. This paper studies track layouts and their applica- tions to other models of graph layout. In particular, we improve on the results of Enomoto and Miyauchi [ SIAM J. Discrete Math. , 1999] regarding stack layouts of subdivisions, and give anal- ogous results for queue layouts. We solve open problems due to Felsner, Wismath, and Liotta [ Proc. Graph Drawing , 2001] and Pach, Thiele, and Toth [ Proc. Graph Drawing , 1997] concern- ing three-dimensional straight-line grid drawings. We initiate the study of three-dimensional polyline grid drawings and establish volume bounds within a logarithmic factor of optimal.