  A \emph{queue layout} of a graph consists of a total order of the vertices,
and a partition of the edges into \emph{queues}, such that no two edges in the
same queue are nested. The minimum number of queues in a queue layout of a
graph is its \emph{queue-number}. A \emph{three-dimensional (straight-line
grid) drawing} of a graph represents the vertices by points in $\mathbb{Z}^3$
and the edges by non-crossing line-segments. This paper contributes three main
results:
  (1) It is proved that the minimum volume of a certain type of
three-dimensional drawing of a graph $G$ is closely related to the queue-number
of $G$. In particular, if $G$ is an $n$-vertex member of a proper minor-closed
family of graphs (such as a planar graph), then $G$ has a $O(1)\times
O(1)\times O(n)$ drawing if and only if $G$ has O(1) queue-number.
  (2) It is proved that queue-number is bounded by tree-width, thus resolving
an open problem due to Ganley and Heath (2001), and disproving a conjecture of
Pemmaraju (1992). This result provides renewed hope for the positive resolution
of a number of open problems in the theory of queue layouts.
  (3) It is proved that graphs of bounded tree-width have three-dimensional
drawings with O(n) volume. This is the most general family of graphs known to
admit three-dimensional drawings with O(n) volume.
  The proofs depend upon our results regarding \emph{track layouts} and
\emph{tree-partitions} of graphs, which may be of independent interest.

Discrete Mathematics;Computational Geometry