Abstract
A kstack layout (respectively, kqueue layout) of a graph consists of a total order of the vertices, and a partition of the edges into k sets of noncrossing (nonnested) edges with respect to the vertex ordering. A ktrack layout of a graph consists of a vertex kcolouring, 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 k such that G has a kstack (kqueue, ktrack) 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 OScript(log n) to OScript(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 kstack, kqueue, and ktrack subdivisions, for all values of k. The number of division vertices per edge in the case of 2queue and 4track subdivisions, namely OScript(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 OScript(log qn(G)) bends per edge.
Original language  English 

Title of host publication  Graph Drawing 
Subtitle of host publication  12th International Symposium, GD 2004 New York, NY, USA, September 29October 2, 2004 Revised Selected Papers 
Editors  János Pach 
Place of Publication  Berlin Germany 
Publisher  Springer 
Pages  133143 
Number of pages  11 
ISBN (Print)  3540245286 
DOIs  
Publication status  Published  1 Dec 2004 
Externally published  Yes 
Event  Graph Drawing 2004  New York, United States of America Duration: 29 Sep 2004 → 2 Oct 2004 Conference number: 12th https://link.springer.com/book/10.1007/b105810 (Proceedings) 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer 
Volume  3383 
ISSN (Print)  03029743 
Conference
Conference  Graph Drawing 2004 

Abbreviated title  GD 2004 
Country/Territory  United States of America 
City  New York 
Period  29/09/04 → 2/10/04 
Internet address 
