Layouts for Plane Graphs on Constant Number of Tracks
share
A 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 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 track number (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.
READ FULL TEXT