We introduce and study so-called track layouts of graphs. A relationship
between this combinatorial structure and several well-known types of graph
layouts is established. For example, our study of track layouts of bounded
treewidth graphs settles an open problem due to Ganley and Heath (2001)
regarding queue layouts of such graphs. Moreover, the study also
establishes that graphs of bounded treewidth have three-dimensional
straight-line grid drawings with linear volume, which represents the
largest known class of graphs with such drawings.
This is joint work with David R. Wood.