20050915
Stacks, queues and tracks: Layouts of graph subdivisions
Publication
Publication
Discrete Mathematics and Theoretical Computer Science , Volume 7  Issue 1
A κstack layout (respectively, κqueue layout) of a graph consists of a total order of the vertices, and a partition of the edges into κ sets of noncrossing (nonnested) edges with respect to the vertex ordering. A κtrack layout of a graph consists of a vertex κcolouring, and a total order of each vertex colour class, such that between each pair of colour classes no two edges cross. The stacknumber (respectively, queuenumber, tracknumber) of a graph G, denoted by sn(G) (qn(G), tn(G)), is the minimum κ such that G has a κstack (κqueue, κtrack) layout. This paper studies stack, queue, and track layouts of graph subdivisions. It is known that every graph has a 3stack subdivision. The best known upper bound on the number of division vertices per edge in a 3stack subdivision of an nvertex graph G is improved from O(log n) to O(log min{sn(G), qn(G)}). This result reduces the question of whether queuenumber is bounded by stacknumber to whether 3stack graphs have bounded queue number. It is proved that every graph has a 2queue subdivision, a 4track subdivision, and a mixed 1stack 1queue subdivision. All these values are optimal for every nonplanar graph. In addition, we characterise those graphs with κstack, κqueue, and κtrack subdivisions, for all values of κ. The number of division vertices per edge in the case of 2queue and 4track subdivisions, namely O(log qn (G)), is optimal to within a constant factor, for every graph G. 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. Finally, we establish a tight relationship between queue layouts and socalled 2track thickness of bipartite graphs.
Additional Metadata  

, , , , , , , , , , , , , ,  
Discrete Mathematics and Theoretical Computer Science  
Organisation  School of Computer Science 
Dujmović, V, & Wood, D. (2005). Stacks, queues and tracks: Layouts of graph subdivisions. Discrete Mathematics and Theoretical Computer Science, 7(1).
