A \emph{ $k$-track} layout of a graph consists of a vertex $k$ colouring, and a total order of each vertex colour class, such that between each pair of colour classes no two edges cross. A \emph{ $k$-queue} layout of a graph consists of a total order of the vertices, and a partition of the edges into $k$ sets such that no two edges that are in the same set are nested with respect to the vertex ordering. The \emph{ track number} (\emph{ queue number}) of a graph $G$, is the minimum $k$ such that $G$ has a $k$-track ($k$-queue) layout. This paper proves that every $n$-vertex plane graph has constant-bound track and queue numbers. The result implies that every plane has a 3D crossing-free straight-line grid drawing in $O(n)$ volume. The proof utilizes a novel graph partition technique.
Categories: cs.CG