Carleton University
Technical Report TR-03-08
October 2003
Stacks, Queues and Tracks: Layouts of Graphs
Abstract
A k-stack layout (respectively, k -queue layout ) of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-crossing (non-nested) edges with respect to the vertex ordering. 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. The stack-number (respectively, queue-number , track-number ) of a graph G , denoted by sn ( G ) ( qn ( G ) , tn ( G ) ), is the minimum k such that G has a k -stack ( k -queue, k -track) layout. This paper studies stack, queue, and track layouts of graph subdivisions. It is known that every graph has a 3 -stack subdivision. The best known upper bound on the number of division vertices per edge in a 3 -stack subdivision of an n -vertex graph G is improved from O (log n ) to O (log min { sn ( G ) , qn ( G ) } ) . This result reduces the question of whether queue-number is bounded by stack-number to whether 3 -stack graphs have bounded queue number. It is proved that every graph has a 2 -queue subdivision, a 4 -track subdivision, and a mixed 1 – stack 1 -queue subdivision. All these values are optimal for every non-planar graph. In addition, we characterise those graphs with k -stack, k -queue, and k -track subdivisions, for all values of k . The number of division vertices per edge in the case of 2 -queue and 4 -track subdivisions, namely O (log qn ( G )) , is optimal to within a constant factor, for every graph G . The relationship between queue layouts and so-called 2 -track thickness of bipartite graphs is investigated, and applications to 3D polyline grid drawings are presented. For example, it is proved that every graph G has a 3D polyline grid drawing with the vertices on a rectangular prism, and with O (log qn ( G )) bends per edge.