Layouts for Plane Graphs on Constant Number of Tracks

Abstract

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.

arXiv admin note: text overlap with arXiv:1302.0304 by other authors