Vida Dujmović

David R Wood
email: david.wood@upc.edu

Stacks, Queues and Tracks: Layouts of Graph Subdivisions †

Keywords: graph layout, graph drawing, track layout, stack layout, queue layout, book embedding, track-number, queue-number, stack-number, page-number, book-thickness, 2-track thickness, geometric thickness, subdivision, three-dimensional graph

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)

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.

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 so-called 2-track thickness of bipartite graphs.

Introduction

We consider undirected, finite, and simple graphs G with vertex set V (G) and edge set E(G). A subdivision of a graph G is a graph obtained from G by replacing each edge vw ∈ E(G) by a path with at least one edge whose endpoints are v and w. Internal vertices on this path are called division vertices, while v and w are called original vertices. Let G ′ , G ′′ and G ′′′ be the subdivisions of G with respectively one, two and three division vertices per edge. Throughout this paper, we implicitly use the fact that planarity and non-planarity is preserved by subdividing edges. A graph H is a minor of G if H is isomorphic to a graph obtained from a subgraph of G by contracting edges. A minor-closed class of graphs is proper if it is not the class of all graphs.

A graph parameter is a function α that assigns to every graph G a non-negative integer α(G). Let G be a class of graphs. By α(G) we denote the function f : N → N, where f (n) is the maximum of α(G), taken over all n-vertex graphs G ∈ G. We say G has bounded α if α(G) ∈ O [START_REF] Mokhtar | Complexities of layouts in threedimensional VLSI circuits[END_REF]. A graph parameter α is bounded by a graph parameter β (for some class G), if there exists a binding function g such that α(G) ≤ g(β(G)) for every graph G (in G). If α is bounded by β (in G) and β is bounded by α (in G) then α and β are tied (in G). Clearly, if α and β are tied then a graph family G has bounded α if and only if G has bounded β. These notions were introduced by Gyárfás [START_REF] Ás | Problems from the world surrounding perfect graphs[END_REF] in relation to near-perfect graph families for which the chromatic number is bounded by the clique-number.

Stack and Queue Layouts

An ordering of a set S is a total order < σ on S. It will be convenient to interchange "σ" and "< σ " when there is no ambiguity. For instance, we say S is ordered by σ. For some ordered set S, let ← -S denote the same set with the reverse ordering. A vertex ordering of a graph G is an ordering σ of the vertex set V (G). At times, it will be convenient to express σ by the list (v 1 , v 2 , . . . , v n ), where v i < σ v j if and only if 1 ≤ i < j ≤ n. Suppose that V 1 , V 2 , . . . , V k are disjoint sets of vertices, such that each V i is ordered by < i . Then (V 1 , V 2 , . . . , V k ) denotes the vertex ordering σ such that v < σ w whenever v ∈ V i and w ∈ V j with i < j, or v ∈ V i , w ∈ V i , and v < i w. We write

V 1 < σ V 2 < σ • • • < σ V k .
In a vertex ordering σ of a graph G, let L(e) and R(e) denote the endpoints of each edge e ∈ E(G) such that L(e) < σ R(e). Consider two edges e, f ∈ E(G) with no common endpoint such that L(e) < σ L(f ). If L(e) < σ L(f ) < σ R(e) < σ R(f ) then e and f cross, and if L(e) < σ L(f ) < σ R(f ) < σ R(e) then e and f nest, and f is nested inside e. A stack (respectively, queue) is a set of edges E ′ ⊆ E(G) such that no two edges in E ′ cross (nest). Observe that when traversing the vertex ordering, edges in a stack (queue) appear in LIFO (FIFO) order-hence the names. A queue E ′ has a total order , called the queue order, such that ∀e, f ∈ E ′ , e f ⇐⇒ L(e) ≤ σ L(f ) and R(e) ≤ σ R(f ) .

(

A k-stack (queue) layout of G consists of a vertex ordering σ of G and a partition {E ℓ : 1 ≤ ℓ ≤ k} of E(G), such that each E ℓ is a stack (queue) in σ. At times we write stack(e) = ℓ (or queue(e) = ℓ) if e ∈ E ℓ . Examples of 3-stack and 3-queue layouts of K 6 are illustrated in Figure 1. A graph admitting a k-stack (queue) layout is called a k-stack (queue) graph. The stack-number of a graph G, denoted by sn(G), is the minimum k such that G is a k-stack graph. The queue-number of a graph G, denoted by qn(G), is the minimum k such that G is a k-queue graph. By interpreting a queue layout as a partition of the edges into sets that satisfy [START_REF] Mokhtar | Complexities of layouts in threedimensional VLSI circuits[END_REF], the queue-number of a graph is a natural measure of its 'linearity'.

For a summary of applications and results regarding stack and queue layouts see our companion paper [START_REF] Vida | On linear layouts of graphs[END_REF]. Despite a wealth of research on stack and queue layouts, the following fundamental questions of Heath et al. [START_REF] Heath | Comparing queues and stacks as mechanisms for laying out graphs[END_REF] remain unanswered.

Open Problem 1. [56] Is stack-number bounded by queue-number?

Open Problem 2. [START_REF] Heath | Comparing queues and stacks as mechanisms for laying out graphs[END_REF] Is queue-number bounded by stack-number? Suppose that stack-number is bounded by queue-number, but queue-number is not bounded by stacknumber. This would happen, for example, if there exists a constant s such that for every q there exists an s-stack graph with no q-queue layout. Then we would consider stacks to be more 'powerful' than queues, and vice versa.

Heath et al. [START_REF] Heath | Comparing queues and stacks as mechanisms for laying out graphs[END_REF], in their study of the relationship between stack-and queue-number, restricted themselves to linear binding functions. For example, for stack-number to be bounded by queue-number meant that sn(G) ∈ O(qn(G)) for every graph G. Thus Heath et al. [START_REF] Heath | Comparing queues and stacks as mechanisms for laying out graphs[END_REF] considered Open Problem 1 to be solved in the negative by displaying an infinite class of graphs G, such that sn(G) ∈ Ω(3 qn(G) ). In our more liberal definition of a binding function, this result merely provides a lower bound on a potential binding function.

Depth-first search and breadth-first search can be thought of as the same algorithm, where depth-first search operates with a stack and breadth-first search operates with a queue. Thus stack and queue layouts of graphs are a means for measuring the relative power of depth-first search and breadth-first search. It is no coincidence that many algorithms for computing stack layouts use depth-first search [START_REF] Fan R | Embedding graphs in books: a layout problem with applications to VLSI design[END_REF][START_REF] Ganley | The pagenumber of k-trees is O(k)[END_REF], while breadth-first search is often used for computing queue layouts [START_REF] Vida Dujmovi | Layout of graphs with bounded treewidth[END_REF][START_REF] Heath | Comparing queues and stacks as mechanisms for laying out graphs[END_REF][START_REF] Madhavan | Stack and queue number of 2-trees[END_REF]. These ideas are made particularly concrete in the case of trees (see Lemmata 15 and 16).

Stack and Queue Layouts of Subdivisions

Stack and queue layouts of graph subdivisions are a central topic of this paper. The following fundamental result has been observed by many authors [START_REF] Oporowski | Drawing subdivisions of complete and complete bipartite graphs on books[END_REF][START_REF] Enomoto | Embedding graphs into a three page book with O(M log N ) crossings of edges over the spine[END_REF][START_REF] Miki Shimabara Miyauchi | An O(nm) algorithm for embedding graphs into a 3-page book[END_REF][START_REF] Miki Shimabara Miyauchi | Embedding a graph into a d + 1-page book with ⌈m log d n⌉ edgecrossings over the spine[END_REF]. The well known proof, which we include for completeness, can be traced to the seminal result by Atneosen [START_REF] Atneosen | On the embeddability of compacta in n-books: intrinsic and extrinsic properties[END_REF] that every graph has an embedding in a 3-page book. Kainen and Overbay [START_REF] Kainen | Book embeddings of graphs and a theorem of Whitney[END_REF] state that, according to Jozef Przytycki, this result was also discovered by Holtz, a student of Reidemeister. Proof: Let σ be an arbitrary vertex ordering of a given graph G. Consider the graph G ′′ with each edge of G subdivided twice. For each vertex v ∈ V (G), insert into σ the vertices {x : vx ∈ E(G ′′ )} immediately to the right of v, and assign the edges E * = {vx : v ∈ V (G), vx ∈ E(G ′′ )} to the first stack. Clearly no two edges in E * cross in σ. It remains to assign a subdivision of the matching E(G ′′ ) \ E * to the remaining two stacks. This amounts to drawing a matching in the plane with no edge crossings such that the vertices are fixed to a line. Clearly this can be accomplished. An edge of E(G ′′ ) \ E * is subdivided every time it crosses the line. Thus every graph has a 3-stack subdivision. ✷

Note that 3-stack layouts are important in complexity theory [START_REF] Zvi Galil | On 3-pushdown graphs with large separators[END_REF][START_REF] Zvi Galil | On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines[END_REF][START_REF] Kannan | Unraveling k-page graphs[END_REF], and 3-stack layouts of knots and links, so called Dynnikov diagrams, have also recently been considered [START_REF] Cromwell | Embedding knots and links in an open book. II. Bounds on arc index[END_REF][START_REF] Dynnikov | Three-page representation of links[END_REF][START_REF] Dynnikov | Three-page approach to knot theory. Coding and local motions[END_REF][START_REF] Dynnikov | A three-page approach to knot theory. The universal semigroup[END_REF][START_REF] Dynnikov | A new way to represent links, one-dimensional formalism and untangling technology[END_REF][START_REF] Kurlin | Three-page Dynnikov diagrams of linked 3-valent graphs[END_REF][START_REF] Morton | Arc index and the Kauffman polynomial[END_REF][START_REF] Vershinin | Three-page embeddings of singular knots. Funktsional[END_REF].

The proof of Theorem 1 provides no bound on the number of division vertices. It is interesting to determine the minimum number of division vertices in a 3-stack subdivision of a given graph. The previously best known bounds are due to Enomoto and Miyauchi [START_REF] Enomoto | Embedding graphs into a three page book with O(M log N ) crossings of edges over the spine[END_REF], who proved that every graph has a 3-stack subdivision with O(log n) division vertices per edge. Moreover, a trade-off between the number of stacks and the number of division vertices per edge was observed. In particular, Enomoto and Miyauchi [START_REF] Miki Shimabara Miyauchi | Trade off between page number and number of edge-crossings on the spine of book embeddings of graphs[END_REF][START_REF] Miki Shimabara Miyauchi | Embedding a graph into a d + 1-page book with ⌈m log d n⌉ edgecrossings over the spine[END_REF] proved that for all s ≥ 3, every graph has an s-stack subdivision with O(log s-1 n) division vertices per edge, and Enomoto et al. [START_REF] Hikoe | Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph[END_REF] proved that this bound is tight up to a constant factor for K n (and some slightly more general families). Thus Enomoto et al. [START_REF] Hikoe | Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph[END_REF] claimed that the O(log n) upper bound is 'essentially best possible'. Note that Miyauchi [START_REF] Miki Shimabara Miyauchi | Book embeddings of bipartite graphs[END_REF] recently improved the upper bound to O(log s-1 n) for bipartite graphs with n vertices in the smaller bipartition.

We prove a refinement of the upper bound of Enomoto and Miyauchi [START_REF] Enomoto | Embedding graphs into a three page book with O(M log N ) crossings of edges over the spine[END_REF], in which the number of division vertices per edge depends on the stack-number or queue-number of the given graph. In particular, every graph G has a 3-stack subdivision with O(log min{sn(G), qn(G)}) division vertices per edge. Since sn(G) and qn(G) are both no more than n, our bound is at most the O(log n) bound of Enomoto and Miyauchi [START_REF] Enomoto | Embedding graphs into a three page book with O(M log N ) crossings of edges over the spine[END_REF] (ignoring constant factors). This result has a significant implication for Open Problem 2. Namely that queue-number is bounded by stack-number if and only if 3-stack graphs have bounded queuenumber (Theorem 8). For this corollary to hold, it is essential that the number of division vertices per edge is some function of sn(G), thus emphasising the significance of our bound in comparison with previous results. As described in Table 1, our result for 3-stack subdivisions generalises to s-stack subdivisions in a similar fashion to the result of Miyauchi [START_REF] Miki Shimabara Miyauchi | Embedding a graph into a d + 1-page book with ⌈m log d n⌉ edgecrossings over the spine[END_REF].

We prove an analogous result for queue layouts. In particular, every graph G has a 2-queue subdivision with O(log qn(G)) division vertices per edge. Thus, at least for the representation of graph subdivisions, two queues suffice rather than three stacks. In this sense, queues are more powerful than stacks. Moreover, our bound on the number of division vertices per edge is optimal up to a constant factor for all graphs. Unfortunately, no such universal lower bound is known for stack layouts of subdivisions.

Stack and queue layouts are generalised through the notion of a mixed layout. Here each edge of a graph is assigned to a stack or to a queue, defined with respect to a common vertex ordering. We speak of an s-stack q-queue mixed layout and an s-stack q-queue graph. Part of the motivation for studying mixed stack and queue layouts is that they model the double-ended queue (dequeue) data structure, since a dequeue may be simulated by two stacks and one queue. Observe that the proof of Theorem 1 implies that every graph has a 2-stack 1-queue subdivision, since the first stack is also a queue, whereas we prove that every graph has a 1-stack 1-queue subdivision. q-queue (q ≥ 2) Θ(log q qn(G)) Theorems 4 and 5 planar 1-queue n -2 Theorem 20 arbitrary s-stack q-queue (s ≥ 1, q ≥ 1)

O(log (s+q)q sn(G)) Theorem 11 arbitrary s-stack q-queue (s ≥ 1, q ≥ 1)

O(log (s+q)q qn(G))

Track Layouts

A vertex t-colouring of a graph G is a partition {V i : 1 ≤ i ≤ t} of V (G) such that for every edge vw ∈ E(G), if v ∈ V i and w ∈ V j then i = j. Suppose that each colour class V i is ordered by < i . Then the ordered set (V i , < i ) is called a track, and {(V i , < i ) : 1 ≤ i ≤ t} is a t-track assignment of G. We say track(v) = i when v ∈ V i .
To ease the notation we denote track assignments by {V i : 1 ≤ i ≤ t} when the ordering on each colour class is implicit. The span of an edge vw in a track assignment {V i : 1 ≤ i ≤ t} is |i -j| where v ∈ V i and w ∈ V j . That there is a fixed ordering of the tracks in a track assignment is implicit in the definition of span.

An X-crossing in a track assignment consists of two edges vw and xy such that v < i x and y < j w, for distinct colours i and j. An edge k-colouring of G is simply a partition {E i : 1 ≤ i ≤ k} of E(G). An edge vw ∈ E i is said to be coloured i, written col(vw) = i. A (k, t)-track layout of G consists of a t-track assignment of G and an edge k-colouring of G with no monochromatic X-crossing. A graph admitting a (k, t)-track layout is called a (k, t)-track graph. The minimum t such that a graph G is a (k, t)-track graph is denoted by tn k (G).

(1, t)-track layouts (that is, with no X-crossing) are of particular interest due to applications in threedimensional graph drawing (see Section 5). A (1, t)-track layout is called a t-track layout. A graph admitting a t-track layout is called a t-track graph. The track-number of G is tn 1 (G), simply denoted by tn(G). For a summary of bounds on the track-number see our companion paper [START_REF] Vida Dujmovi | Track layouts of graphs[END_REF].

The following lemma highlights the fundamental relationship between track layouts, and queue and stack layouts. Its proof follows immediately from the definitions, and is illustrated in Figure 2 The relationship between queue and track layouts in Lemma 1 was extended by Dujmović et al. [START_REF] Vida Dujmovi | Track layouts of graphs[END_REF] who proved that queue-number and track-number are tied.

Our main result concerning track layouts highlights the trade-off between few tracks and few edge colours. We prove that every graph G has a subdivision D with O(log qn(G)) division vertices per edge, such that (a) D has a (1, 4)-track layout, (b) D has a (2, 3)-track layout, and (c) D has a (3, 2)-track layout. We shall see that all of these numeric values are best possible for any non-planar graph G. Moreover, the number of division vertices per edges is optimal, since any subdivision satisfying (a), (b) or (c) has an edge with Ω(log qn(G)) division vertices. For all d ≥ 2, our results generalise to (1, d + 2)-, (d, 3)-, and (d + 1, 2)-track layouts as summarised in Table 1.

Thickness and Topological Parameters

Let α be a graph parameter. Let sub-α be the graph parameter defined by sub-α(G) = α(G ′ ) for every graph G. We say α is topological if α and sub-α are tied. For example, chromatic number is not topological since G ′ is bipartite. On the other hand treewidth is topological. In fact, it is well known that the treewidth of a graph G equals the treewidth of every subdivision of G [23, Exercise 13,p. 278].

The thickness of a graph G, denoted by θ(G), is the minimum number of subgraphs in a partition of E(G) into planar subgraphs [START_REF] Kainen | Thickness and coarseness of graphs[END_REF]. Thickness is not topological since θ(G ′ ) ≤ 2. Beineke [START_REF] Beineke | Biplanar graphs: a survey[END_REF] attributes this observation to Tutte. The proof is straightforward. Let V (G) = {v 1 , v 2 , . . . , v n }. Denote by x i,j the division vertex of each edge v i v j with i < j. Then {v i x i,j : 1 ≤ i < j ≤ n} and {v i x j,i : 1 ≤ j < i ≤ n} is a partition of E(G ′ ) in two (planar) forests.

The geometric thickness of a graph G, denoted by θ(G), is the minimum number of colours such that G can be drawn in the plane with edges as coloured straight-line segments, such that monochromatic edges do not cross [START_REF] Dillencourt | Geometric thickness of complete graphs[END_REF][START_REF] Kainen | Thickness and coarseness of graphs[END_REF]. Every graph G has such a drawing in the plane with an arbitrary set of preassigned vertex locations, and with θ(G) edge colours [START_REF] Halton | On the thickness of graphs of given degree[END_REF][START_REF] Wenger | Embedding planar graphs at fixed vertex locations[END_REF]. Thus, the key difference between geometric thickness and (graph-theoretic) thickness is that geometric thickness requires the edges to be drawn as straight line-segments, whereas thickness allows edges to bend arbitrarily. Eppstein [START_REF] David Eppstein | Separating thickness from geometric thickness[END_REF] proved that θ(G ′ ) ≤ 2 for every graph G. Thus geometric thickness is not topological.

Stack-number (or book-thickness) is equivalent to geometric thickness with the additional requirement that the vertices are in convex position [START_REF] Bernhart | The book thickness of a graph[END_REF]. Thus

∀ graph G, θ(G) ≤ θ(G) ≤ sn(G) . (2)
Blankenship and Oporowski [START_REF] Oporowski | Drawing subdivisions of complete and complete bipartite graphs on books[END_REF], Enomoto and Miyauchi [START_REF] Enomoto | Embedding graphs into a three page book with O(M log N ) crossings of edges over the spine[END_REF], and Eppstein [START_REF] David Eppstein | Separating thickness from geometric thickness[END_REF] independently proved that sn(K n ) is bounded by sn(K ′ n ). The proofs by Blankenship and Oporowski [START_REF] Oporowski | Drawing subdivisions of complete and complete bipartite graphs on books[END_REF] and Eppstein [START_REF] David Eppstein | Separating thickness from geometric thickness[END_REF] use essentially the same Ramsey-theoretic argument. Since θ(K ′ n ) = 2, Eppstein [START_REF] David Eppstein | Separating thickness from geometric thickness[END_REF] observed that stacknumber is not bounded by geometric thickness. Using a more elaborate Ramsey-theoretic argument, Eppstein [START_REF] David Eppstein | Separating thickness from geometric thickness[END_REF] proved that geometric thickness is not bounded by thickness. In particular, for every t there exists a graph with thickness three and geometric thickness at least t. Blankenship and Oporowski [START_REF] Oporowski | Drawing subdivisions of complete and complete bipartite graphs on books[END_REF] conjecture that their result for complete graphs extends to all graphs.

Conjecture 1. [7]

There exists a function f , such that for every graph G and every subdivision H of G with at most one division vertex per edge, we have sn(G) ≤ f (sn(H)).

In Lemma 13 we prove that sub-sn is bounded by sn. Thus the truth of Conjecture 1 would imply that stack-number is topological. Moreover, in Theorem 10 we prove that if Conjecture 1 is true then stack-number is bounded by queue-number, thus giving an affirmative solution to Open Problem 1. In Sections 2.1 and 2.2 we prove that both track-number and queue-number are topological.

We now relate queue-number to a new thickness parameter. Let the 2-track thickness of a bipartite graph G, denoted by θ 2 (G), be the minimum k such that G has a (k, 2)-track layout. By (2) and Lemma 1(c),

∀ bipartite graphs G, θ(G) ≤ θ(G) ≤ sn(G) ≤ θ 2 (G) .
Let the 2-track sub-thickness of a graph G, denoted by sub-θ 2 (G), be the 2-track thickness of G ′ . This is well-defined since G ′ is bipartite. In Theorem 2 we prove that queue-number is tied to 2-track thickness for bipartite graphs, and queue-number is tied to 2-track sub-thickness (for all graphs). The immediate implication for Open Problem 1 is that stack-number is bounded by queue-number if and only if stack-number is bounded by 2-track sub-thickness. While it is an open problem whether stack number is bounded by track-number or by queue-number, in our companion paper [START_REF] Vida Dujmovi | Track layouts of graphs[END_REF] we prove the weaker result that geometric thickness is bounded by track-number, which implies that geometric thickness is bounded by queue-number.

Three-Dimensional Polyline Drawings

A three-dimensional polyline grid drawing of a graph, henceforth called a 3D polyline drawing, represents the vertices by distinct points in Z 3 (called gridpoints), and represents each edge as a polyline between its endpoints with bends (if any) also at gridpoints, such that distinct edges only intersect at common endpoints, and each edge only intersects a vertex that is an endpoint of that edge. A 3D polyline drawing with at most b bends per edge is called a 3D b-bend drawing. A 3D 0-bend drawing is called a 3D straightline drawing. Of course, a 3D b-bend drawing of a graph G is precisely a 3D straight-line drawing of a subdivision of G with at most b division vertices per edge.

In contrast to the case in the plane, it is well known that every graph has a 3D straight-line drawing. We therefore are interested in optimising certain measures of the aesthetic quality of such drawings. The bounding box of a 3D polyline drawing is the minimum axis-aligned box containing the drawing. If the bounding box has side lengths X -1, Y -1 and Z -1, then we speak of an X × Y × Z polyline drawing with volume X • Y • Z. That is, the volume of a 3D polyline drawing is the number of gridpoints in the bounding box. This definition is formulated so that two-dimensional drawings have positive volume.

This paper initiates the study of upper bounds on the volume and number of bends per edge in arbitrary 3D polyline drawings. (Three-dimensional polyline graphs drawings with orthogonal edges have been previously studied; see [START_REF] Peter Eades | Three dimensional orthogonal graph drawing algorithms[END_REF][START_REF] Wood | Optimal three-dimensional orthogonal graph drawing in the general position model[END_REF] for example.) The volume of 3D straight-line drawings has been widely studied [START_REF] Bose | The maximum number of edges in a three-dimensional grid-drawing[END_REF][START_REF] Sterbini | 3D straight-line grid drawing of 4-colorable graphs[END_REF][START_REF] Cohen | Three-dimensional graph drawing[END_REF][START_REF] Di | Drawing series-parallel graphs on restricted integer 3D grids[END_REF][START_REF] Di | Drawing series-parallel graphs on a box[END_REF][START_REF] Di | Track drawings of graphs with constant queue number[END_REF][START_REF] Vida Dujmovi | Layout of graphs with bounded treewidth[END_REF][START_REF] Vida | Three-dimensional grid drawings with sub-quadratic volume[END_REF][START_REF] Stefan Felsner | Straight-line drawings on restricted integer grids in two and three dimensions[END_REF][START_REF] Toru Hasunuma | Laying out iterated line digraphs using queues[END_REF][START_REF] Ános | Three-dimensional grid drawings of graphs[END_REF][START_REF] Timo Poranen | A new algorithm for drawing series-parallel digraphs in 3D[END_REF]. Three-dimensional graph drawings in which the vertices are allowed real coordinates have also been investigated [START_REF] Ingo Bruß | Fast interactive 3-D graph visualization[END_REF][START_REF] Kiran | Three-dimensional Tutte embedding[END_REF][START_REF] Marek Chrobak | Convex drawings of graphs in two and three dimensions[END_REF][START_REF] Cruz | 3D graph drawing with simulated annealing[END_REF][START_REF] Peter Eades | Drawing stressed planar graphs in three dimensions[END_REF][START_REF] Garg | Drawing with colors[END_REF][START_REF] Hong | Drawing graphs symmetrically in three dimensions[END_REF][START_REF] Eades | An algorithm for finding three dimensional symmetry in series parallel digraphs[END_REF][START_REF] Eades | Drawing trees symmetrically in three dimensions[END_REF][START_REF] Hong | Linkless symmetric drawings of series parallel digraphs[END_REF][START_REF] Hong | Drawing algorithms for series-parallel digraphs in two and three dimensions[END_REF][START_REF] Burkhard Monien | A parallel simulated annealing algorithm for generating 3D layouts of undirected graphs[END_REF][START_REF] Diethelm | Some Three-Dimensional Graph Drawing Algorithms[END_REF]. Aesthetic criteria besides volume that have been considered include symmetry [START_REF] Hong | Drawing graphs symmetrically in three dimensions[END_REF][START_REF] Eades | An algorithm for finding three dimensional symmetry in series parallel digraphs[END_REF][START_REF] Eades | Drawing trees symmetrically in three dimensions[END_REF][START_REF] Hong | Linkless symmetric drawings of series parallel digraphs[END_REF][START_REF] Hong | Drawing algorithms for series-parallel digraphs in two and three dimensions[END_REF], aspect ratio [START_REF] Marek Chrobak | Convex drawings of graphs in two and three dimensions[END_REF][START_REF] Garg | Drawing with colors[END_REF], angular resolution [START_REF] Marek Chrobak | Convex drawings of graphs in two and three dimensions[END_REF][START_REF] Garg | Drawing with colors[END_REF], edge-separation [START_REF] Marek Chrobak | Convex drawings of graphs in two and three dimensions[END_REF][START_REF] Garg | Drawing with colors[END_REF], and convexity [START_REF] Kiran | Three-dimensional Tutte embedding[END_REF][START_REF] Marek Chrobak | Convex drawings of graphs in two and three dimensions[END_REF][START_REF] Peter Eades | Drawing stressed planar graphs in three dimensions[END_REF]. Three-dimensional graph drawing has applications in software visualisation [START_REF] Dwyer | Three dimensional UML using force directed layout[END_REF][START_REF] Parker | Visualization of large nested graphs in 3D: Navigation and interaction[END_REF][START_REF] Franck | Viewing a graph in a virtual reality display is three times as good as a 2D diagram[END_REF][START_REF] Franck | Evaluating stereo and motion cues for visualizing information nets in three dimensions[END_REF][START_REF] Ware | Layout for visualizing large software structures in 3D[END_REF][START_REF] Ware | Visualizing object oriented software in three dimensions[END_REF] and VLSI circuit layout [START_REF] Mokhtar | Complexities of layouts in threedimensional VLSI circuits[END_REF][START_REF] Aggarwal | Multilayer grid embeddings for VLSI[END_REF][START_REF] Leighton | Three-dimensional circuit layouts[END_REF][START_REF] Leighton | Three-dimensional circuit layouts[END_REF][START_REF] Nishioka | An automatic routing system for high density multilayer printed wiring boards[END_REF][START_REF] Franco | Optimal three-dimensional VLSI layouts[END_REF][START_REF] Rosenberg | Three-dimensional VLSI: A case study[END_REF][START_REF] So | Some theoretical results on the routing of multilayer printed-wiring boards[END_REF][START_REF] Wood | Bounded degree book embeddings and three-dimensional orthogonal graph drawing[END_REF] for example.

Table 2 summarises the best known upper bounds on the volume and bends per edge in 3D polyline drawings, including those established in this paper. In general, there is a tradeoff between few bends and small volume in such drawings, which is evident in Table 2. Our upper bound of O(m log q) is within a factor of O(log q) of being optimal for all q-queue graphs, since Bose et al. [START_REF] Bose | The maximum number of edges in a three-dimensional grid-drawing[END_REF] proved that 3D polyline drawings have at least 1 8 (n + m) volume. O(m log q) Theorem 28

Organisation

This paper is organised as follows. Section 2 presents results regarding queue, stack and track layouts of the subdivisions G ′ and G ′′ . Section 3 presents most of our main results discussed above. In Section 3.2 we review known results concerning stack and queue layouts of trees, and prove a useful lemma about mixed stack and queue layouts of trees. Section 4 considers layouts of subdivisions of planar graphs. Finally, in Section 5 we present applications in three-dimensional polyline graph drawing.

Small Subdivisions

In this section we consider layouts of G ′ and G ′′ , the subdivisions of a graph G with one and two division vertices per edge, respectively.

Track Layouts

Lemma 2. For every q-queue graph G, the subdivision G ′ has a (q + 1, 2)-track layout. That is, 2-track sub-thickness is bounded by queue-number. In particular, sub-θ 2 (G) ≤ qn(G) + 1.

Proof: Let σ be the vertex ordering in a q-queue layout of G with queues {E ℓ : 1 ≤ ℓ ≤ q}. Recall that L(e) and R(e) denote the left and right endpoints in σ of each edge e. Let X(e) denote the division vertex of e in G ′ . Let ≺ be the total order on {X(e) : e ∈ E(G)} such that X(e) ≺ X(f ) whenever L(e) < σ L(f ), or L(e) = L(f ) and R(e) < σ R(f ). Consider (V (G), σ) and ({X(e) : e ∈ E(G)}, ≺) to define a 2-track assignment of G ′ . Colour the edges of G ′ as follows. For all edges e ∈ E ℓ , let col(L(e)X(e)) = 0 and col(X(e)R(e)) = ℓ. Since in ≺, division vertices are ordered primarily by the left endpoint of the corresponding edge, no two edges L(e)X(e) and L(f )X(f ) form an X-crossing. Suppose e ′ = X(e)R(e) and f ′ = X(f )R(f ) form an X-crossing. Without loss of generality R(e) < σ R(f ) and X(f ) ≺ X(e). By construction L(f ) < σ L(e), and e is nested inside f in σ. Thus e and f are in distinct queues, and col(e ′ ) = col(f ′ ). Hence there is no monochromatic X-crossing. The number of edge colours is q + 1. Therefore we have a (q + 1, 2)-track layout of G ′ . ✷ Lemma 2 is best possible in the following (weak) sense. Let G be a 2-queue subdivision of a nonplanar graph, which exists by Theorem 4 below. If G ′ has a (k, 2)-track layout, then k ≥ 3 since G ′ is non-planar, and by Theorem 22 below, only planar graphs have (2, 2)-track layouts. In Lemma 3 below we prove a complimentary result to Lemma 2.

Lemma 3. Queue-number is bounded by 2-track sub-thickness. In particular, if sub-θ 2 (G) ≤ k for some graph G, then qn(G) ≤ 1 2 k(k + 1)
.

Proof: Clearly we can assume that G is connected. Thus in the given

(k, 2)-track layout of G ′ ,
2 + k = 1 2 k(k + 1). ✷
The observant reader will notice parallels between the above proof and that of the Erdös-Szekeres Theorem [START_REF] George Szekeres | A combinatorial problem in geometry[END_REF] regarding increasing and decreasing subsequences. In fact, the Erdös-Szekeres Theorem in conjunction with Lemma 23 below can prove Lemma 3 with the slightly weaker bound of qn(G) ≤ k 2 .

Theorem 2. Queue-number is tied to 2-track thickness for bipartite graphs, and queue-number is tied to 2-track sub-thickness (for all graphs).

Proof: The first claim is proved in our companion paper [START_REF] Vida Dujmovi | Track layouts of graphs[END_REF]. The second claim follows from Lemmata 2 and 3. ✷ Lemma 4. Every c-colourable q-queue graph G satisfies:

(a) tn 2 (G ′ ) ≤ q + 1, (b) tn(G ′ ) ≤ c(q + 1)
, and (c) tn(G ′′ ) ≤ q + 2 .

Proof: Let σ be the vertex ordering in a q-queue layout of G with queues {E ℓ : 1 ≤ ℓ ≤ q}. Let X(e) denote the division vertex of e in G ′ . Let X ℓ = {X(e) : e ∈ E ℓ } for each 1 ≤ ℓ ≤ q. Let < ℓ denote the queue order of each E ℓ . Consider < ℓ to also order X ℓ . That is, for all edges e, f ∈ E ℓ ,

X(e) ≤ ℓ X(f ) ⇐⇒ L(e) ≤ σ L(f ) and R(e) ≤ σ R(f ) . (3)
First we prove (a). The set {(X ℓ , < ℓ ) : 1 ≤ ℓ ≤ q} ∪ {(V (G), σ)} defines a (q + 1)-track assignment of G ′ . Colour edges L(e)X(e) of G ′ blue, and colour edges R(e)X(e) of G ′ red. We claim that there is no monochromatic X-crossing. All edges of G ′ are between a vertex of G and a division vertex. Thus an X-crossing must involve two division vertices on the same track. Consider two edges e and f with X(e) < ℓ X(f ) for some 1 ≤ ℓ ≤ q. By (3), each of the pairs of edges {L(e)X(e), L(f )X(f )} and {R(e)X(e), R(f )X(f )} do not form an X-crossing. For each pair of edges {L(e)X(e), R(f )X(f )} and {R(e)X(e), L(f )X(f )} the edges are coloured differently. Thus there is no monochromatic X-crossing and we have a

(2, q + 1)-track layout of G ′ . Now we prove (b). Let {V i : 1 ≤ i ≤ c} be a vertex c-colouring of G. Let X i,ℓ = {X(e) : e ∈ E ℓ , L(e) ∈ V i } for all 1 ≤ ℓ ≤ q and 1 ≤ i ≤ c. Thus {(X i,ℓ , < ℓ ) : 1 ≤ i ≤ c, 1 ≤ ℓ ≤ q} ∪ {(V i , < σ ) : 1 ≤ i ≤ c} defines a (qc + c)-track assignment of G ′ . Consider division vertices X(e), X(f ) ∈ X i,ℓ such that X(e) < ℓ X(f ). By (3), L(e) ≤ L(f ) in the ordering on V i .
Thus the pair of edges {L(e)X(e), L(f )X(f )} do not form an X-crossing. Since both R(e) and R(f ) are not in V i , the pairs of edges {L(e)X(e), R(f )X(f )} and {R(e)X(e), L(f )X(f )} do not form an X-crossing. If both R(e) and R(f ) are in the same colour class V j , then R(e) ≤ j R(f ) by ( 3), and the pair of edges {R(e)X(e), R(f )X(f )} do not form an X-crossing. Thus we have a (qc + c)-track layout of G ′ .

Finally we prove (c). Let (L(e), X(e), Y (e), R(e)) be the path replacing each edge e in G ′′ . The first track consists of {(V (G), σ)}. The second track consists of {X(e) : e ∈ E(G)}, ordered so that X(e) < X(f ) whenever L(e) < σ L(f ), or L(e) = L(f ) and R(e) < σ R(f ). Edges between the first and second track are of the form L(e)X(e). Since vertices X(e) in the second track are primarily ordered by L(e), there is no X-crossing between the first and second track. Now define and order Y ℓ as with X ℓ . Then (Y ℓ , < ℓ ) : 1 ≤ ℓ ≤ q} comprises the final q tracks. An X-crossing involving vertices on these tracks can only be between pairs of edges {X(e)Y (e), X(f )Y (f )} or {Y (e)R(e), Y (f )R(f )}, where e and f are in the same queue. By [START_REF] Atneosen | On the embeddability of compacta in n-books: intrinsic and extrinsic properties[END_REF], such pairs of edges do not form an X-crossing. Thus we have (q + 2)-track layout of G ′′ . ✷

We now describe how to produce a track layout of G ′ given a track layout of a graph G. We will need the following result from our companion paper [START_REF] Vida Dujmovi | Track layouts of graphs[END_REF].

Lemma 5. [28]

Queue-number is bounded by track-number. In particular, every (k, t)-track graph with maximum span s (≤ t -1) has a ks-queue layout.

Lemma 6. Let G be a (k, t)-track graph with maximum span s (≤ t -1). Then (a) tn ks+1 (G ′ ) ≤ 2, (b) tn k (G ′ ) ≤ 2t -1, and (c) tn(G ′ ) ≤ k(t -1) + t . Proof: Let {V i : 1 ≤ i ≤ t} be a (k, t)-track layout of G with span s. Let {E ℓ : 1 ≤ ℓ ≤
k} be the corresponding edge-colouring. By Lemma 5, G has a ks-queue layout. By Lemma 4(a), G ′ has a (ks + 1, 2)-track layout. This proves part (a).

For each edge vw of G, let both edges in G ′ corresponding to vw be coloured by the colour assigned to vw. Now we prove part (b). For each the division vertices of edges vw ∈ E(G) such that v ∈ V i , w ∈ V j , and i < j. Order the vertices in X i with respect to the order of the corresponding vertices in V i , breaking ties by the order in some V j where applicable. Clearly there is no monochromatic X-crossing, where vertices of G \ G ′ remain in the given track layout. The number of tracks is 2t -1.

1 ≤ i ≤ t -1, let X i ⊆ V (G ′ ) \ V (G) be the set consisting of G (V (G), σ) {X(e) : e ∈ E(G)} Y 1 Y 2 Y 3
Finally we prove part (c). For each

1 ≤ i ≤ t -1 and 1 ≤ ℓ ≤ k, let X i,ℓ ⊆ X i be the set consisting of the division vertices of edges vw ∈ E ℓ such that v ∈ V i , w ∈ V j , and i < j. Order each X i,ℓ as in X i .
All edges of G ′ incident to a vertex in X i,ℓ are monochromatic. Thus there is no X-crossing regardless of the edge colours. The number of tracks is t + k(t -1).

✷

We now describe how to produce a track layout of a graph G given a track layout of G ′ .

Lemma 7.

If a graph G is vertex c-colourable and G ′ has a (k, t)-track layout, then G has a (tk 2 , ct)track layout.

Proof:

Let {V i : 1 ≤ i ≤ c} be a vertex c-colouring of G, and for each vertex v ∈ V (G), let col(v) = i where v ∈ V i . Let {(W j , < j ) : 1 ≤ j ≤ t} be a (k, t)-track layout of G ′ with edge colouring {E ℓ : 1 ≤ ℓ ≤ k}. Let V i,j = V i ∩W j for each 1 ≤ i ≤ c and 1 ≤ j ≤ t. Then {(V i,j , < j ) : 1 ≤ i ≤ c, 1 ≤ j ≤ t} is a track assignment of G.
We now colour each edge vw of G. Without loss of generality col(v) < col(w).

Let x be the division vertex of vw in G ′ , and say x ∈ W j , vx ∈ E ℓ1 , and wx ∈ E ℓ2 . Then colour vw by the ordered triple (j, ℓ 1 , ℓ 2 ). Note that the number of edge colours is tk 2 . We claim that there is no monochromatic X-crossing in the track assignment of G. Suppose for the sake of contradiction, that there are monochromatic edges vw and pq in G that form an X-crossing. Without loss of generality, col(v) = col(p) < col(w) = col(q), and in the given track layout of G ′ , v < j1 p and q < j2 w for some 1 ≤ j 1 , j 2 ≤ t. Let x and y be the division vertices of vw and pq, respectively. Since vw and pq are monochromatic, x and y are in the same track W j3 . If x < j3 y then wx and qy form a monochromatic X-crossing in the given track layout, and if y < j3 x then vx and py form a monochromatic X-crossing in the given track layout. In both cases we have the desired contradiction. Thus there is no monochromatic X-crossing in the track assignment of G, and we have a

(tk 2 , ct)-track layout of G. ✷ Lemma 8. For every graph G, if tn(G ′ ) ≤ t then G is vertex t(2t -1)-colourable.
Proof: Consider a t-track layout of G ′ . For 1 ≤ i ≤ t, let V i be the set of original vertices of G on the i-th track. Let G i be the subgraph of G induced by V i . Let E i,j be the set of edges vw of G for which v, w ∈ V i and the division vertex of vw is in the j-th track of G ′ (1 ≤ j ≤ t, j = i). Each vertex in V i is incident to at most two edges in E i,j , as otherwise there would be an X-crossing in the track layout of G ′ . Thus G i has maximum degree at most 2(t -1). Hence G i is (2t -1)-colourable, and G is t(2t -1)-colourable. ✷ Theorem 3. Track-number is topological. In particular, every graph G satisfies

tn(G ′ ) ≤ 2 tn(G) -1 ,
and if tn(G ′ ) ≤ t then tn(G) ≤ (2t -1)t 2 • 4 ( t 2 )((2t-1)t 2 -1)
.

Proof: The first claim is Lemma 6(c) with k = 1. Now suppose that tn(G ′ ) ≤ t. By Lemma 8, G is t(2t -1)-colourable. By Lemma 7 with k = 1 and c = t(2t -1), G has a (t, t 2 (2t -1))-track layout.

In our companion paper [START_REF] Vida Dujmovi | Track layouts of graphs[END_REF], we proved that a (k ′ , t ′ )-track layout of a graph G can be refined to an

(edge-monochromatic) t ′ • 4 ( k ′ 2 )(t ′ -1) -track layout of G.
The lemma follows by applying this result with k ′ = t and t ′ = t 2 (2t -1). ✷

Queue Layouts

In this section we study the relationship between the queue-number of a graph G and the queue-number of G ′ . First note that Lemmata 2 and 5 imply the following.

Lemma 9.

The subdivision G ′ of a q-queue graph G has a (q + 1)-queue layout. ✷

We have the following converse result.

Lemma 10. For every graph G, if G ′ has a q-queue layout with vertex ordering σ, then σ restricted to V (G) admits a q(2q + 1)-queue layout of G.

Proof: Let X be the set of division vertices of G ′ . In our companion paper [START_REF] Vida Dujmovi | Track layouts of graphs[END_REF], we prove that for every vertex colouring {V i : 1 ≤ i ≤ c} of a q-queue graph H, there is a (2q, c)-track layout of H with tracks {V i : 1 ≤ i ≤ c}. Now apply this result to G ′ . The vertex sets V (G) and X define a vertex 2-colouring of G ′ . Thus G ′ has a (2q, 2)-track layout with tracks (V (G), σ) and (X, σ). That is, sub-θ 2 (G) ≤ 2q. By Lemma 3, σ restricted to V (G) admits a q(2q + 1)-queue layout of G. ✷ Lemmata 9 and 10 imply that queue-number is topological, as mentioned in Section 1.4. We now prove a slightly more general result than Lemma 10 that will be used in Section 3.5. Here we start with a subdivision with at most one division vertex per edge rather than exactly one division vertex per edge. Lemma 11. Let D be a q-queue subdivision of a graph G with at most one division vertex per edge. Then G has a 2q(q + 1)-queue layout.

Proof: Let σ be the vertex ordering in a q-queue layout of D. Let A be the set of edges of G that are subdivided in D, and let B the set of edges of G that are not subdivided in D. By Lemma 10, G[A] has a q(2q + 1)-queue layout with vertex ordering σ. By assumption, G[B] has a q-queue layout with vertex ordering σ. Thus G has a 2q(q + 1)-queue layout with vertex ordering σ. ✷

Stack Layouts

We now describe how to produce a stack layout of G ′ from a queue, stack or track layout of G. By Lemmata 1(c) and 2 we have:

Lemma 12. The subdivision G ′ of a q-queue graph G has a (q + 1)-stack layout. That is, sn(G ′ ) ≤ qn(G) + 1. ✷ Lemma 13. The subdivision G ′ of an s-stack graph G has an (s + 1)-stack layout. That is, sn(G ′ ) ≤ sn(G) + 1.
Proof: Consider an s-stack layout of G with vertex ordering σ. Denote the division vertex of e in G ′ by X(e). We now create a stack layout of G ′ . For each vertex v of G, let e 1 , e 2 , . . . , e d be all the edges incident to v such that each L(e i ) = v, and R(e

d ) < σ R(e d-1 ) < σ • • • < σ R(e 1 )
. Add the division vertices X(e 1 ), X(e 2 ), . . . , X(e d ) immediately to the right of v in this order. Clearly for all edges e and f of G, the edges L(e)X(e) and L(f )X(f ) of G ′ do not cross. Thus all these 'left' edges can be assigned to a single stack. Each 'right' edge X(e)R(e) of G ′ inherits the stack assigned to e in G. Clearly no two right edges in the same stack cross. Thus G ′ has a (s + 1)-stack layout. ✷ Lemma 14. Let G be a (k, t)-track graph with maximum span s (≤ t -1). Then the subdivision G ′ of G with one division vertex per edge has an s(k + 1)-stack layout.

Proof: Let {(V i , < i ) : 1 ≤ i ≤ t} be a (k, t)
-track layout of G with maximum span s, and with edge colouring {E ℓ : 1 ≤ ℓ ≤ k}. Denote by L(e) and R(e) the endpoints of each edge e of G where L(e) ∈ V i and R(e) ∈ V j with i < j. Denote by X(e) the division vertex in G ′ of e. For each

1 ≤ i ≤ t -1 and 1 ≤ α ≤ s, let X i,α = {X(e) : e ∈ E(G), L(e) ∈ V i , R(e) ∈ V i+α } .
Since the maximum span is s, every division vertex of G ′ is in some X i,α . Order each X i,α such that for all X(e), X(f ) ∈ X i,α , we have X(e) < X(f ) whenever L(f ) < i L(e), or L(e) = L(f ) and R(f ) < i+α R(e). Let σ be the vertex ordering of G ′ defined by

V 1 , X 1,s , X 1,s-1 , . . . , X 1,1 ; V 2 , X 2,s , X 2,s-1 , . . . , X 2,1 ; . . . ; V t .
Note that L(e) < σ X(e) < σ R(e) for every edge e of G. For all 1 ≤ α ≤ s let

E α = {L(e)X(e) : L(e) ∈ V i , X(e) ∈ X i,α } . For all 1 ≤ ℓ ≤ k and 0 ≤ β ≤ s -1, let E ℓ,β = {X(e)R(e) : e ∈ E ℓ , L(e) ∈ V i , i ≡ β (mod s)} .
This partitions the edges of G ′ into s(k + 1) sets. We claim that no two edges in a single set cross in σ.

Consider two edges e and f of G. Say L(e) ∈ V i1 and L(f ) ∈ V i2 . Consider edges L(e)X(e) and L(f )X(f ) both in some E α . Without loss of generality i 1 ≤ i 2 , and if

L(e) = L(f ) then R(e) < σ R(f ). If i 1 < i 2 then L(e) < σ X(e) < σ L(f ) < σ X(f ),
and L(e)X(e) and L(f )X(f ) do not cross. If i 1 = i 2 then without loss of generality L(e) ≤ σ L(f ). Since L(e)X(e) and L(f )X(f ) are in E α , both X(e) and X(f ) are in X i1,α . Thus L(e) ≤ σ L(f ) < σ X(f ) < σ X(e), and L(f )X(f ) does not cross L(e)X(e). Thus each set E α is a valid stack in σ.

Now suppose the edges X(e)R(e) and X(f )R(f ) cross in σ. Without loss of generality X(e) < σ X(f

) < σ R(e) < σ R(f ). Say R(e) ∈ V i3 and R(f ) ∈ V i4 . Then i 1 ≤ i 2 < i 3 ≤ i 4 . If i 1 < i 2 then i 2 -i 1 < i 3 -i 1 ≤ s. Thus i 1 ≡ i 2 (mod s)
, and X(e)R(e) and X(f )R(f ) are not in the same E ℓ,β . Now suppose i 1 = i 2 . Since X(e) < σ X(f ), we have i 3 = i 4 and L(f

) ≤ i1 L(e). If L(f ) = L(e) then, since X(e) < σ X(f ) we have R(f ) < i3 R(e), and thus R(f ) < σ R(e), a contradiction. If L(f ) < i1 L(e) then R(e) < i3 R(f ) since R(e) < σ R(f ).
That is, e and f form an X-crossing in the track layout, and are thus coloured differently. Hence X(e)R(e) and X(f )R(f ) are not in the same E ℓ,β .

Thus each E α and each E ℓ,β is a valid stack, and G ′ has a s(k + 1)-stack layout. ✷

Big Subdivisions

In this section we prove the main results introduced in Section 1. That is, every graph G has a 3-stack subdivision, a 2-queue subdivision, a mixed 1-stack 1-queue subdivision, and a 4-track subdivision. In each case the number of division vertices per edge is O(log sn(G)) or O(log qn(G)). First of all we introduce the notion of a (k, H)-layout.

(k, H)-Layouts

Let G and H be graphs. H is called a host graph, and its vertices are called nodes.

An H-partition of G is a partition {H x ⊆ V (G) : x ∈ V (H)} of V (G)
into bags indexed by the nodes of H such that for all edges vw ∈ E(G) either:

-∃ node x ∈ V (H) such that both v, w ∈ H x (vw is called an intrabag edge mapped to x), or -∃ edge xy ∈ E(H) such that v ∈ H x and w ∈ H y (vw is called an interbag edge mapped to xy).

Tree-partitions, that is a T -partition for some tree T , have been widely studied [START_REF] Bodlaender | Domino treewidth[END_REF][START_REF] Oporowski | Some results on tree decomposition of graphs[END_REF][START_REF] Oporowski | On tree-partitions of graphs[END_REF][START_REF] Halin | Tree-partitions of infinite graphs[END_REF][START_REF] Detlef Seese | Tree-partite graphs and the complexity of algorithms[END_REF], and were instrumental in the result by Dujmović et al. [START_REF] Vida Dujmovi | Layout of graphs with bounded treewidth[END_REF] that track-number and queue-number are bounded by treewidth.

To obtain our main results for layouts of subdivisions we employ the following general structure. A

(k, H)-layout of G is a pair ({E 1 , E 2 , . . . , E k }, {(H x , < x ) : x ∈ V (H)}) such that: -{H x ⊆ V (G) : x ∈ V (H)} is an H-partition of G. -∀ nodes x ∈ V (H), < x is a total order on H x .
-{E 1 , . . . , E k } is a colouring of the interbag edges such that there is no monochromatic X-crossing, where an X-crossing consists of a pair of interbag edges vw and pq such that for some edge xy ∈ E(H), v < x p and q < y w.

For each edge xy ∈ E(H), let k xy denote the number of colours used in the edge colouring of the interbag edges of G that are mapped to xy. For each node x ∈ V (H), let s x denote the minimum number of stacks such that < x admits an s x -stack layout of G[H x ], and let q x denote the minimum number of queues such that < x admits a q x -queue layout of G[H x ].

A (k, H)-layout with no intrabag edges is called a (k, H)-track layout. A (1, H)-track layout is called an H-track layout. Observe that a (k, K t )-track layout is simply a (k, t)-track layout as defined in Section 1.3.

Our main results are proved using the following strategy. First a particular host tree T (or tree-like graph T ) is defined. The vertices of our graph G are mapped to the root of T , and each edge vw of G is mapped to some node of T . At each non-root node of T on the path from the root to the node that vw is mapped to, we add two division vertices to vw. This process produces a (k, T )-layout of a subdivision D of G, and is described in Section 3.3. Then a stack, queue, mixed or track-layout of T is determined, as described in Section 3.2. Then in Section 3.4 we describe how to transform a given layout of T into the desired layout of D. This process is then carried out for queue, stack, mixed, and track layouts in Sections 3.5-3.8.

Layouts of Trees

Let T be a rooted tree. The vertices of T are called nodes, and we assume that the edges are oriented away from the root node r. This will be the case for the remainder of this paper. A node in T with no outgoing edge is a leaf in T . As is standard, when referring to the edge of a directed graph, xy means an edge oriented from x to y. The depth of a node x ∈ V (T ) is the distance from r to x in T , and is denoted by depth(x). The height of T is the maximum depth of a node in T . Let deg(x), deg -(x), and deg + (x) denote the degree, indegree, and outdegree of each node x ∈ V (T ). We denote by ρ(x) the parent node of each non-root node x ∈ V (T ). A vertex ordering σ of T is breadth-first if for all nodes x, y ∈ V (T ), x < σ y whenever depth(x) < depth(y), or depth(x) = depth(y) and ρ(x) < σ ρ(y).

Lemma 15. [57]

A breadth-first vertex ordering of a tree T admits a 1-queue layout of T .

Proof: Since the depths of adjacent nodes differ by exactly one, and the nodes are ordered by nondecreasing depth, the endpoints of a nested pair of edges must be at consecutive depths. By construction, such a pair of edges are not nested, as illustrated in Figure 4. A depth-first vertex ordering σ of a rooted tree T is defined recursively as follows. Let r be the root node of T with child nodes x 1 , x 2 , . . . , x d . Let T i be the subtree rooted at x i , 1 ≤ i ≤ d. Then σ is defined by σ(T ) = (r, σ(T 1 ), σ(T 2 ), . . . , σ(T d )).

✷ depth 0 depth 1 depth 2 depth 3

Lemma 16. [16]

A depth-first vertex ordering σ of a tree T admits a 1-stack layout of T .

Proof: For the sake of contradiction, suppose that a pair of edges vw and xy cross in σ. Without loss of generality v < σ x < σ w < σ y. Since w is a child of v and v < σ x < σ w, we have that x (and y) are in some subtree T i rooted at a child v i of v. Since x < σ w we have V (T i ) < σ w. Since y ∈ V (T i ), we have y < σ w, which is the desired contradiction. Thus no two edges cross in σ, as illustrated in Figure 5. ✷ The next lemma is the starting point for our results on mixed layouts in Section 3.7. An edge 2colouring of a tree T with colours red and black is good, if for each node x ∈ V (T ) with an incoming red edge, no other edge incident to x is red. A vertex ordering of a directed graph is topological if all edges are directed from left to right.

Lemma 17.

Let T be a rooted tree with a good edge 2-colouring. Then T has a topological vertex ordering in which the red edges form a stack, and the black edges form a queue.

Proof: Let h be the height of T . For each 0 ≤ d ≤ h, let V d be the set of nodes of T at depth d.

For each 1 ≤ d ≤ h, let R d and B d denote the sets of nodes in V d with an incoming red and black edge, respectively. Let σ be the vertex ordering (V 0 , R 1 , B 1 , R 2 , B 2 , . . . , R h , B h ) of T , where for each 1 ≤ d ≤ h, the nodes in B d are ordered with respect to the order of their parents (in V d-1 ), and the nodes in R d are in reverse order to that of their parents (in V d-1 ). More precisely, for all v, w ∈ B d we have v < σ w whenever ρ(v) < σ ρ(w), and for all v, w ∈ R d we have v < σ w whenever ρ(w) < σ ρ(v).

Since the depths of adjacent nodes differ by exactly one, and the nodes are ordered by non-decreasing depth, the endpoints of a nested pair of edges must be at consecutive depths. By construction, such a pair of black edges are not nested. Hence the black edges form a queue.

Suppose, for the sake of contradiction, that the red edges vw and pq cross. Without loss of generality v < σ p < σ w < σ q. Then depth(v) ≤ depth(p) ≤ depth(w). Since depth(w) = depth(v) + 1, either depth(p) = depth(v) or depth(p) = depth(v) + 1. First suppose that depth(p) = depth(v). Then depth(q) = depth(w). Since both q and w have incoming red edges, q < σ w by construction. This is a contradiction. Now suppose that depth(p) = depth(v)+1. Then depth(p) = depth(w). Let d = depth(p). Since p has an outgoing red edge pq, the incoming edge at p is black, and p ∈ B d . Now w ∈ R d since w has an incoming red edge vw. Since R d < σ B d , we have w < σ p, which is the desired contradiction. Thus no two red edges cross, and hence the red edges form a stack. ✷

The next result is implicit in the work of Felsner et al. [START_REF] Stefan Felsner | Straight-line drawings on restricted integer grids in two and three dimensions[END_REF].

Lemma 18. [44]

Every rooted tree T has an (edge-monochromatic) track layout in which every edge has span one.

Proof: Let σ be a breadth-first vertex ordering of T starting at the root. Let V d be the set of nodes at depth d. It is easily seen that there are no X-crossings in the track layout {(V d , σ) : d ≥ 0}. Clearly every edge has span one, as illustrated in Figure 6.

✷ V 3 V 2 V 1 V 0
Fig. 6: Track layout of a complete binary tree with every edge having span 1.

(k, T )-Layouts

Lemma 19. Let T be the tree comprised of a root node r and d ≥ 1 leaves v 1 , v 2 , . . . , v d adjacent to r. Suppose that the nodes of T are labelled with non-negative integers l(r), l(v 1 ), l(v 2 ), . . . , l(v d ). Let G be a graph with a k-queue (respectively, k-stack) layout with vertex ordering σ, where k ≤ l(r)

+ l(v 1 ) + l(v 2 ) + • • • + l(v d ).
Then G has a subdivision D with zero or two division vertices per edge such that D has a (1, T )-layout in which the division vertices are mapped to the leaves of T , and the original vertices are mapped to the root r and are ordered by σ. Furthermore, every node x ∈ V (T ) has q x ≤ l(x) (s x ≤ l(x)).

Proof:

Say σ = (v 1 , v 2 , . . . , v n ). Let l be an integer such that k -l ≤ l(v 1 ) + l(v 2 ) + • • • + l(v d ).
Let F be the set of edges of G in an arbitrary set of l queues (stacks). Subdivide every edge e = vw ∈ E(G) \ F twice, and denote the resulting path by (v, e v , e w , w). This defines a subdivision D of G with zero or two division vertices per edge. For each vertex v ∈ V (G), let

N + (v) = {e v : e ∈ E(G) \ F, v = L σ (e)} and N -(v) = {e v : e ∈ E(G) \ F, v = R σ (e)}.
Order the vertices of N + (v) and N -(v) with respect to the order of the neighbours of v in σ as follows. In the case of a given queue layout, let π be the vertex ordering of V (D) \ V (G) defined by

π = N + (v 1 ), N -(v 2 ), N + (v 2 ), N -(v 3 ), N + (v 3 ), . . . , N -(v n-1 ), N + (v n-1 ), N -(v n ) .
For a given stack layout, let π be the vertex ordering of V (D) \ V (G) defined by

π = ← ----- N + (v 1 ), ← ----- N -(v 2 ), ← ----- N + (v 2 ), ← ----- N -(v 3 ), ← ----- N + (v 3 ), . . . , ← ------- N -(v n-1 ), ← ------- N + (v n-1 ), ← ----- N -(v n ) .
Partition the remaining kl queues (stacks) of G into sets A 1 , A 2 , . . . , A d so that each A i has at most l(v i ) queues (stacks). Create a (1, T )-layout of D as follows. Map the original vertices ordered by σ to r. By construction, the intrabag edges F of D mapped to r form l queues (stacks) with respect to σ. Thus q r ≤ l (s r ≤ l). For each edge vw ∈ E(G) \ F that is in a queue (stack) in A i , map e v and e w to v i . Order each bag T vi by π. Since π is ordered primarily with respect to σ, there is no X-crossing in the layout. That is, we have a (1, T )-layout of D. In this layout, the edges e v e w of D are intrabag edges mapped to the leaves of T . Consider each such edge e v e w to be assigned to the same queue (stack) as vw in the given layout of G. Consider two edges e = vw and f = xy in E(G) \ F that have no common endpoint. Since π is ordered primarily with respect to σ, the edges e v e w and f x f y nest/cross in π if and only if e and f nest/cross in σ. Now consider two edges e = vx and f = vy in E(G) \ F (that have a common endpoint). In the case of queues, e v e x and f v f y are either crossing or disjoint. For stacks, e v e x and f v f y are either nested or disjoint. Thus the queue (stack) assignment for intrabag edges is valid, and

q vi ≤ l(v i ) (s vi ≤ l(v i )) for each 1 ≤ i ≤ d. ✷
For the next result we will need the following construction. Let G be a graph with a (k 1 , T 1 )-layout for some tree T 1 . Let x be a node of T 1 , and suppose that the subgraph G[T 1x ] has a subdivision D x where D x has a (k 2 , T 2 )-layout, for some tree T 2 such that all the original vertices of D x are mapped to the root r of T 2 ordered by < x . Let merge-at-x be a binary operation on the layouts (k 2 , T 2 ) and (k 1 , T 1 ) defined as follows. First replace (T x , < x ) by (T r , < r ), and rename x to y. Delete r from T 2 and make its children point to y. Each node z = y in the new tree T 3 inherits (T z , < z ) from the node it originated from. It follows from the definition that merging (k 2 , T 2 ) and (k 1 , T 2 ) at x results in a (k 3 , T 3 )-layout of the subdivision D of G where k 3 ≤ max{k 1 , k 2 } and where q y = q r (s y = s r ), and each node z = y in V (T 3 ) has q z (s z ) equal to that of the node it originated from. Lemma 20. Let T be a rooted tree of height h. Suppose that each node x ∈ V (T ) is labelled by a nonnegative integer l(v) such that v∈V (T ) l(v) ≥ k. Let G be a k-queue (respectively, k-stack) graph. Then G has a subdivision D with an even number of division vertices per edge, such that D has a (1, T )-layout in which every node x ∈ V (T ) has q x ≤ l(x) (s x ≤ l(x)). Every edge of G has at most 2h division vertices in D, and if all the non-leaf nodes of T are labelled 0 and if all its leaves are at depth h, then every edge of G has exactly 2h division vertices in D.

Proof:

We proceed by induction on h. If h = 0 then the result follows trivially. Assume the result holds for all trees with height less than h, and let T be a tree of height h rooted at r. Let T ′ be the subtree of T induced by the nodes at depth at most h -1. Define a labeling on the nodes of T ′ as follows. For each node x ∈ V (T ′ ) at depth h -1, let l ′ (x) = l(x) + l(x 1 ) + l(x 2 ) + • • • + l(x d ) where x 1 , x 2 , . . . , x d are the children of x in T . For all remaining nodes x ∈ V (T ′ ), let l ′ (x) = l(x). Now x∈V (T ′ ) l ′ (x) = x∈V (T ) l(x) ≥ k. Thus by induction, G has a subdivision D ′ with at most 2(h -1) division vertices per edge, and D has a (1, T ′ )-layout such that q x ≤ l ′ (x) (s x ≤ l ′ (x)) for all nodes x ∈ V (T ′ ). For each node x ∈ V (T ) at depth h -1, let T (x) denote the subtree of T induced by x and its children, and let each node of T (x) inherit its label from T . For every leaf node x ∈ V (T ′ ) at depth h -1, apply Lemma 19 to the l ′ (x)-queue (stack) layout (D ′ [T ′ x ], < x ) and the labelled tree T (x). Merging(-at-x) the resulting (1, T (x))-layout of D ′ [T ′

x ] with the (1, T ′ )-layout of D ′ (for every leaf node x) gives rise to the desired (1, T )-layout of a subdivision D of G. Since only the intrabag edges in the leaf nodes of T ′ are subdivided and they are subdivided either zero or two times, D is a subdivision of G with an even number of division vertices per edge. Moreover, D has at most 2h division vertices per edge. The final claim of the lemma is immediate from the construction. Figure 7 illustrates the main concepts of the proof. ✷ For all integers d 1 , d 2 > 0, a complete (d 1 , d 2 )-ary tree is a rooted tree in which all the leaves are at the same depth, every non-leaf node at even depth has outdegree d 1 and every non-leaf node at odd depth has outdegree d 2 . If d 1 = d 2 = d then we speak of a complete d-ary tree. The following special case of Lemma 20 will be useful. We say a (k, T )-layout of G is simple if for every non-leaf node x ∈ V (T ), the set T x is an independent set of G. Thus for simple layouts, q x = s x = 0 for all non-leaf nodes. Lemma 21. Let T be a subdivision of the complete (d 1 , d 2 )-ary tree of height h. Let h ′ be the height of T . Let α = (d 1 ) ⌈h/2⌉ (d 2 ) ⌊h/2⌋ . Then every k-queue (respectively, k-stack) graph G has a subdivision D with an even number of division vertices per edge, and D has a simple (1, T )-layout in which q x ≤ ⌈k/α⌉ (s x ≤ ⌈k/α⌉)) for every node x ∈ V (T ). Moreover, the number of division vertices per edge is at most 2h ′ , or exactly 2h ′ if all the leaves of T are at depth h ′ .

1 0 1 1 1 (a) (b) (c) (d)
Proof: Let l(x) = 0 for each non-leaf node x ∈ V (T ). Let l(x) = ⌈k/α⌉ for each leaf node x ∈ V (T ). The number of leaves in the complete (d 1 , d 2 )-ary tree of height h is α. Subdividing the edges of a tree does not change the number of leaves. Thus T also has α leaves. Therefore x∈V (T ) l(x) ≥ k. Since the non-leaf nodes are labelled 0, by Lemma 20, G has a subdivision D with a (1, T )-layout such that for each leaf node x ∈ V (T ), q x ≤ l(x) = ⌈k/α⌉ (s x ≤ l(x) = ⌈k/α⌉), and for each non-leaf node x ∈ V (T ), q x ≤ l(x) = 0 (s x ≤ l(x) = 0). Thus the (1, T )-layout is simple. The claim about the number of division vertices per edge follows immediately from Lemma 20. ✷

(k, H)-Layout → Layout of G

For a graph G with a (k, H)-layout, we now show how to convert a layout of H into a layout of G. First consider a (k, T )-layout in which T is a rooted directed tree. We will often define a 2-colouring of the edges of T using colours red and black. The edges of G mapped to red edges of T will be associated with stacks, and those mapped to black edges of T will be associated with queues. Let E r (T ) and E b (T ) denote the sets of red and black edges of T .

Lemma 22.

Let G be a graph with a (k, T )-layout for some rooted tree T . Suppose that each edge and node of T is coloured red or black such that T has a topological vertex ordering σ where the red edges form a stack and the black edges form a queue. For each node x ∈ V (T ), let s ′ x = s x if x is red, and

s ′ x = 0 if x is black. Similarly, let q ′ x = q x if x is black, and q ′ x = 0 if x is red. Let λ s = max x∈V (T )    s ′ x + xy∈E r (T ) k xy + yx∈E r (T ) k yx    , and
λ q = max x∈V (T )    q ′ x + max y∈V (T ) : y≤σx yz∈E b (T ) : x≤σz k yz    .
Then G has an λ s -stack λ q -queue mixed layout, such that the edges of G that are mapped to red nodes or edges of T are in stacks, and the edges of G that are mapped to black nodes or edges of T are in queues.

To prove Lemma 22 we need the following lemma due to Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF]. (See our companion paper [START_REF] Vida | On linear layouts of graphs[END_REF] for a simple proof.) Let σ be a vertex ordering of a graph G. A rainbow in σ is a matching

{v i w i ∈ E(G) : 1 ≤ i ≤ k} such that v 1 < σ v 2 < σ • • • < σ v k < σ w k < σ w k-1 < σ • • • < σ w 1 .

Lemma 23. [57] A vertex ordering of a graph G admits a k-queue layout of G if and only if it has no (k + 1)-edge rainbow.

Proof of Lemma 22: First we label the nodes of T as forward or backward. Consider the nodes of T in the order of their appearance in σ. Label the root node as forward or backward arbitrarily. Now consider a non-root node x with incoming edge yx. Since σ is topological, y has already been labelled. If yx is black then label x with the same label as that given to y. If yx is red then label x with the opposite label to that given to y. Now create a vertex ordering π of G by replacing each node x in σ by T x if x is forward, and by ← -T x if x is backward. (Recall that ← -T x is the reverse ordering of T x to that in the given (k, T )-layout.)

Let E r (G) and E b (G) denote the sets of edges of G that are mapped to red edges/nodes and black edges/nodes of T , respectively. We first prove that there is an edge λ q -colouring of E b (G) such that no two monochromatic edges in E b (G) are nested in π.

Let R be a rainbow in π formed from the edges of E b (G) and with the maximum number of edges. Let the set of intrabag edges in R be denoted by R intra , and the set of interbag edges be denoted by R inter . Then |R| = |R intra | + |R inter |. Suppose the left endpoint of the innermost edge of R is mapped to node x. Then the right endpoint of each edge in R is mapped to a node z such that x ≤ σ z. Intrabag edges mapped to distinct nodes of T are not nested (and not crossing). Thus all the edges in R intra are mapped to the same node of T . Hence all the edges of R intra (if any) are mapped to x. Thus |R intra | ≤ q ′

x . At least one of the endpoints of each edge in R inter is not mapped to x. Thus by the construction of π, such endpoints appear in π either before or after all the endpoints of the edges in R intra . Therefore the edges of R intra are all nested inside the innermost edge of R inter . Since the black edges in T are not nested in σ, all the edges of R inter have an endpoint mapped to the same node y ∈ T . Since the edges in R intra are nested inside the edges of R inter , y ≤ σ x. Furthermore, since σ is a topological vertex-ordering of T , each edge of R inter is mapped to some outgoing edge of y. If two edges of R inter are mapped to the same edge incident to y, then by Lemma 1(b) they may be nested only if their edge colours in the (k, T )-layout are different. Therefore, |R inter | ≤ z∈V (T ) : x≤σz k yz and thus |R| ≤ q ′

x + z∈V (T ) : x≤σz k yz . By considering all choices of x and y ≤ σ x in V (T ), we conclude that a rainbow in π formed by the edges of E b (G) may have at most λ q edges. By Lemma 23, the edges of E b (G) can be coloured with λ q colours such that no two monochromatic edges are nested.

We now define an edge λ s -colouring of E r (G). We then prove that no two monochromatic edges in E r (G) cross. Consider the nodes of T in the order of their appearance in σ. For each node x, colour the edges of G that are mapped to the red edges incident to x as follows. Two interbag edges of G that are mapped to the same outgoing red edge of x receive the same colour if and only if they belong to the same colour class E i ∈ {E 1 , E 2 , . . . E k } in the (k, T )-layout of G. Two interbag edges of G mapped to two distinct red edges incident to x always receive distinct colours (regardless of whether they are incoming or outgoing). If x is red, colour the intrabag edges mapped to x with distinct colours to those used on the interbag edges mapped to the red edges incident to x, and so that < x admits an s x -stack layout of G[T x ]. We now show that λ s colours suffices for such a colouring. If the incoming edge yx of x is red the edges of G mapped to yx use k yx colours out of λ s colours, otherwise 0 out of λ s colours are used. Thus we have either λ sk yx or λ s colours available for colouring the edges of G mapped to x and the red outgoing edges xy 1 , xy 2 , . . . , xy p incident to x. Clearly we can colour the edges of G mapped to xy 1 , xy 2 , . . . , xy p and x as described above with

k xy1 + k xy2 + • • • + k xyp + s ′
x distinct colours. Thus the number of colours used is at most λ s .

We now show that no two monochromatic edges e 1 , e 2 ∈ E r (G) cross in π. That is, monochromatic edges in E r (G) can be in the same stack. From the description of the edge colouring, it is clear that if either e 1 or e 2 is an intrabag edge then the pair does not form a monochromatic crossing. Thus it suffices to consider pairs of interbag edges. Since the red edges in T are not crossing in σ, the only pairs of interbag edges that can create a monochromatic crossing are those with endpoints in the same bag T x . In that case, if e 1 and e 2 are mapped to the same edge incident to x then e 1 and e 2 do not cross by Lemma 1(c). If e 1 and e 2 are mapped to two distinct edges incident to x then e 1 and e 2 are not monochromatic. ✷ Lemma 24. Let H be a graph with a t-track layout {V i : 1 ≤ i ≤ t} such that each node in track 4). We now prove that there are no monochromatic X-crossings with this edge p-colouring. Consider two monochromatic edges e 1 , e 2 ∈ E(G). If e 1 and e 2 are mapped to the same edge of H then by the above colouring procedure and by the properties of the edge colouring in the (k, H)-track layout of G, edges e 1 and e 2 do not form a monochromatic X-crossing. If e 1 and e 2 are mapped to two edges xy, zq ∈ E(H) that have no endpoint in common, then e 1 and e 2 do not form a monochromatic X-crossing since xy and zq do not form a monochromatic X-crossing in the t-track layout of H. Finally, if e 1 and e 2 are mapped to two edges xy, xz ∈ E(H) that share an endpoint x, then e 1 and e 2 can only form a monochromatic X-crossing if y and z are in the same track V ℓ . Say x ∈ V i . Since x has at most one neighbour in V 1 , V 2 , . . . , V i-1 , we have that ℓ > i. Therefore, by the above colouring procedure e 1 and e 2 do not have the same colour. ✷ Lemma 25. Let d ≥ 1 be an integer. Let G be a graph with a simple (1, T 0 )-layout for some tree T 0 , such that every leaf node x has q x ≤ c for some c ≥ 0, and every non-leaf node x has q x = 0 and deg + (x) = d. Then there is a tree T , such that the subdivision D obtained from G by subdividing each intrabag edge once has a (c + 1, T )-track layout in which every node x ∈ V (T ) has

V i , 1 ≤ i ≤ t,
xy∈E(T ) k xy + yx∈E(T ) k yx ≤ max{d + 1, c + 2}, and
xy∈E(T ) k xy ≤ max{d, c + 1} . (5)
Proof: For every leaf node x ∈ V (T 0 ), let D x be the subdivision of G[T 0x ] obtained by subdividing each edge of G[T 0x ] once. By the proof of Lemma 2, D x has a (c + 1, T * )-track layout where T * is a single edge comprised of a root node adjacent to one leaf, such that all the original vertices of G[T 0x ] are mapped to the root and are ordered by < x , and all the division vertices are mapped to the leaf node in T * . For each leaf node x ∈ V (T 0 ), merge-at-x the (1, T 0 )-layout of G and the

(c + 1, T * )-track layout of G[T 0x ].
In the resulting (c + 1, T )-layout of D there are no intrabag edges. Thus we have a (c + 1, T )-track layout, where T is the subdivision of T 0 with each leaf-edge of T 0 subdivided once. Let V ℓ be the set of leaves in T . Let E ℓ be the set of edges of T with an endpoint in V ℓ . All the interbag edges of D that are mapped to the edges in E ℓ are coloured with at most c + 1 colours. All the interbag edges of D that are mapped to the edges in E \ E ℓ are coloured with one colour. Thus, each node x ∈ V (T ) that has no neighbour in V ℓ satisfies [START_REF] Bernhart | The book thickness of a graph[END_REF]. Each node x ∈ V (T ) that has a neighbour in V ℓ has degree at most 2. Since the incoming edge yx of x has k yx ≤ 1 and its outgoing edge xv has k xv ≤ c + 1, x satisfies (5). Finally, each leaf node x has k yx ≤ c + 1 where yx is the incoming edge of x. Thus x satisfies (5). ✷

Queue Layouts

Lemma 26. For every graph G, G ′′ has queue-number qn(G ′′ ) ≤ 2⌈ qn(G)⌉.

Proof:

Let d = ⌈ qn(G)⌉.
Let T be the complete d-ary tree of height 1; that is, the d-ary star. By Lemma 21, G ′′ has a simple (1, T )-layout in which the root node r has deg + (r) = d and q r = 0, and every leaf node x ∈ V (T ) has q x ≤ ⌈qn(G)/d⌉ ≤ d. Let all the edges and nodes of T be coloured black.

Let σ be the vertex ordering of T starting with the root, followed by the leaves. Define λ q as in Lemma 22.

That is, λ q is the maximum, taken over all nodes x ∈ V (T ), of

q x + max y∈V (T ) : y≤σx yz∈E(T ) : x≤σz k yz . (6)
For leaf nodes x, (

k xy ≤ max{d, 2} ≤ d . (7)
Let all the edges and nodes of T be coloured black. By Lemma 15, T has a topological vertex ordering σ that admits a 1-queue layout. Define λ q as in Lemma 22. By [START_REF] Oporowski | Drawing subdivisions of complete and complete bipartite graphs on books[END_REF] and since every node x in T has q x = 0, we have

λ q = max x∈V (T )    q x + max y∈V (T ) : y≤σx yz∈E(T ) : x≤σz k yz    ≤ max x∈V (T )    xv∈E(T ) k xv    ≤ d . (8)
Therefore, by Lemma 22, D has a d-queue layout, as illustrated in Figure 8 for d = 2. ✷

We now prove that the number of division vertices per edge in Theorem 4 is optimal up to a constant factor. Lemma 27. Let D be a q-queue subdivision of a graph G with at most k division vertices per edge. Then G has a ( 1 2 (2q + 2) 2k -1)-queue layout.

Proof: Let q i = 1 2 (2q + 2) 2 i -1, and k i = k/2 i . We proceed by induction on i ≥ 0 with the hypothesis: there exists a subdivision D i of G with at most k i division vertices per edge, and D i has a q i -queue layout. Consider the base case with i = 0. Let D 0 = D. Then D 0 is a subdivision of G with k 0 = k division vertices per edge, and D 0 has a q 0 -queue layout, since q 0 = q.

Suppose that there exists a subdivision D i of G with at most k i division vertices per edge, and D i has a q i -queue layout. By contracting every second division vertex on the path representing each edge of G in D i , we obtain a graph D i+1 such that D i is a subdivision of D i+1 with at most one division vertex per edge, and D i+1 is a subdivision of G with at most k i /2 division vertices per edge. By Lemma 11, D i+1 has a 2q i (q i +1)-queue layout. Now k i /2 = k i+1 , and

2q i (q i +1) ≤ 2(q i +1) 2 -1 = 1 2 (2q+2) 2 i+1 -1 = q i+1 .

Thus the inductive hypothesis holds for all i.

With i * = ⌊log 2 k⌋ + 1, we have k i * < 1. The only subdivision of G with less than one division vertex per edge is G itself. Thus G has a q i * -queue layout, and

q i * = 1 2 (2q + 2) (2 ⌊log 2 k⌋+1 ) -1 ≤ 1 2 (2q + 2) (2 1+log 2 k ) -1 ≤ 1 2 (2q + 2) 2k -1. ✷ Theorem 5.
Let D be a d-queue subdivision of a graph G for some d ≥ 2. Then there is an edge of G with at least 1 6 log d qn(G) division vertices in D.

Proof: Let k be the maximum number of division vertices in D in a single edge of G. By Lemma 27, G has

( 1 2 (2d + 2) 2k -1)-queue layout. Thus qn(G) ≤ 1 2 (2d + 2) 2k -1, and qn(G) ≤ 1 2 (3d) 2k -1 since d ≥ 2. That is, k ≥ 1 2 log 3d 2(qn(G) + 1) = 1 2 (log 3d d)(log d 2(qn(G) + 1)) ≥ 1 6 log d 2(qn(G) + 1) since d ≥ 2. Therefore k ≥ 1
6 log d qn(G), as claimed. Note that log 3d d → 1 for large d, and the lower bound on k tends to 1 2 log d 2(qn(G) + 1). ✷

Queue Layouts and Graph Embeddings

An embedding of a graph G into a connected 'host' graph H is an injection φ : V (G) → V (H). The dilation of an edge vw ∈ E(G) is the distance between φ(v) and φ(w) in H. The dilation of φ is the maximum dilation of an edge of G. For each edge vw ∈ E(G), fix a path of minimum length from φ(v) to φ(w) in H, called the vw-path of φ. Let X be the set of vertices of H that are internal on some vw-path.

The degree of φ is the maximum degree of a vertex in X. Of course, the degree of φ is no more than the maximum degree of H. For example, let H be a subdivision of a graph G with at most k division vertices per edge. Then there is an obvious embedding of G into H with dilation k + 1 and degree 2. Thus the following result provides a generalisation of Lemma 27.

Theorem 6. If a graph G has an embedding φ into a k-queue graph H with dilation d and degree ∆, then G has queue-number

qn(G) ≤ 2k(∆ + 1) (2k(∆ + 1)) d -1 2k(∆ + 1) -1 -k(2∆ + 1) .
Moreover, for every ∆ ≥ 3 and even d ≥ 2, there exists a graph G, a 1-queue graph H, and an embedding of G into H with dilation d, degree ∆, and

qn(G) ≥ ∆((∆ -1) d/2 -1) 2(∆ -2) .
Proof: Let X be the set of vertices of H that are internal on some vw-path of φ. Let D be a copy of H. Let X ′ be the set of vertices of D that are not internal on every vw-path of φ. Now subdivide every edge of D that is incident to a vertex x ∈ X ′ , and then delete x from D. Clearly the maximum degree of D is ∆. By Vizing's Theorem [START_REF] Vadim | On an estimate of the chromatic class of a p-graph[END_REF], D has a proper edge colouring with ∆ + 1 colours. Using the obvious bijection between edges of H and D, let col(xy) denote the colour assigned to each edge xy of H. Let σ be the vertex ordering in a k-queue layout of H. Let queue(xy) denote the queue containing each edge xy of H.

Orient each edge vw of G from v to w, where φ(v) < σ φ(w). For each oriented edge vw of G, fix a path P (vw) from φ(v) to φ(w) in H consisting of at most d edges. Suppose P (vw) = x 0 , x 1 , . . . , x ℓ , where φ(v) = x 0 , φ(w) = x ℓ , and ℓ ≤ d. For each 1 ≤ i ≤ ℓ, let dir(x i-1 x i ) be '+' if x i-1 < σ x i , and '-' otherwise. If ℓ = 1 then let queue(vw) = queue(x 0 x 1 ); otherwise let queue(vw) be the vector of triples

queue(vw) = queue(x i-1 x i ), col(x i-1 x i ), dir(x i-1 x i ) : 1 ≤ i ≤ ℓ .
We claim that this is a valid queue-assignment for G using the vertex ordering σ restricted to {φ(v) : v ∈ V (G)}. Suppose that queue(vw) = queue(pq) for distinct edges vw and pq of G. Then |P (vw)| = |P (pq)|. Let P (vw) = x 0 , x 1 , . . . , x ℓ and P (pq) = y 0 , y 1 , . . . , y ℓ . If ℓ = 1 then queue(x 0 x 1 ) = queue(y 0 y 1 ), and thus vw and pq are not nested. Now assume ℓ ≥ 2.

We have col(x i-1 x i ) = col(y i-1 y i ) for all 1 ≤ i ≤ ℓ. For each 1 ≤ i ≤ ℓ -1, x i and y i are internal vertices on P (vw) and P (pq) respectively, and thus x i ∈ X and y i ∈ X. Edges of H incident to a common vertex in X are coloured differently. Thus x i = y i for all 1 ≤ i ≤ ℓ -1. Without loss of generality x 0 < σ y 0 , or x 0 = y 0 and x 1 < σ y 1 . Since queue(vw) = queue(pq), we have that dir(x 0 x 1 ) = dir(y 0 y 1 ), and x 0 x 1 and y 0 y 1 are not nested.

First suppose that dir(x 0 x 1 ) is '+'. Then x 0 < σ x 1 and y 0 < σ y 1 . Since x 1 = y 1 , and since x 0 x 1 and y 0 y 1 are not nested, either x 0 < σ x 1 < σ y 0 < σ y 1 or x 0 ≤ σ y 0 < σ x 1 < σ y 1 . In both cases, x 1 < σ y 1 . Now suppose that dir(x 0 x 1 ) is '-'. Then x 1 < σ x 0 and y 1 < σ y 0 . Since x 1 = y 1 , and since x 0 x 1 and y 0 y 1 are not nested, either x 1 < σ x 0 < σ y 1 < σ y 0 or x 1 < σ y 1 < σ x 0 ≤ σ y 0 . In both cases, x 1 < σ y 1 .

Thus by induction, for all 1 ≤ i ≤ ℓ, we have that x i < σ y i (or x ℓ = y ℓ ). Thus x ℓ ≤ σ y ℓ . Thus in G we have v ≤ σ p and w ≤ σ q. That is, vw and pq are not nested. Thus we have a valid queue-assignment for G. The number of queues is

k + d ℓ=2 (2k(∆ + 1)) ℓ = k + 2k(∆ + 1) (2k(∆ + 1)) d -1 2k(∆ + 1) -1 -2k(∆ + 1) = 2k(∆ + 1) (2k(∆ + 1)) d -1 2k(∆ + 1) -1 -k(2∆ + 1) .
Now for the lower bound. Let T ∆,h be the tree of height h ≥ 1 in which every non-leaf node has degree ∆ ≥ 3, and every leaf node is at height h. Let n be the number of nodes in T ∆,h . Then

n = 1 + ∆ h-1 i=0 (∆ -1) i = 1 + ∆ (∆ -1) h -1 ∆ -2 = ∆(∆ -1) h -2 ∆ -2 .
By Lemma 15, qn(T ∆,h ) = 1. Any embedding of G = K n into T ∆,h has dilation d = 2h and degree ∆.

Since qn(K n ) = ⌊ n 2 ⌋, we have qn(G) ≥ n -1 2 = ∆(∆ -1) h -∆ 2(∆ -2) = ∆((∆ -1) d/2 -1) 2(∆ -2) . ✷
Theorem 6 implies that to prove that a family of graphs F has bounded queue-number, it suffices to demonstrate that every graph in F has a bounded-dilation embedding into a graph with bounded degree and bounded queue-number. We have the following example of Theorem 6, which will be of particular interest if Open Problem 4 is solved in the affirmative. A drawing of a graph G represents the vertices by distinct points in the plane, and represents each edge by a simple Jordan curve between its endpoints. The only vertices that an edge may intersect are its own endpoints. At most two edges may cross at a single point, edges only cross properly, and no two edges may overlap. Theorem 8. The following are equivalent:

(1) queue-number is bounded by stack-number,

(2) bipartite 3-stack graphs have bounded queue-number,

(3) bipartite 3-stack graphs have bounded 2-track thickness.

Moreover, if queue-number is bounded by stack-number then queue-number is bounded by a polynomial function of stack-number.

Proof: That (1) implies ( 2) is immediate. Theorem 2 proves that (2) and (3) are equivalent. It remains to prove that (2) implies [START_REF] Mokhtar | Complexities of layouts in threedimensional VLSI circuits[END_REF]. Suppose that every bipartite 3-stack graph has queue-number at most some constant q. Consider an arbitrary graph G. By Lemma 13, G ′ has a (sn(G) + 1)-stack layout. Thus, by Theorem 7, G ′ has a 3-stack subdivision D with 2⌈log 2 (sn(G)+1)⌉-2 division vertices per edge. That is, G has a 3-stack subdivision with 2(2⌈log 2 (sn(G)+1)⌉-2)+1 = 4⌈log 2 (sn(G)+1)⌉-3 division vertices per edge. Since every edge of G is subdivided an odd number of times, D is bipartite. By assumption, D has queue-number at most q. By Lemma 27, G has queue-number at most 1 2 (2q+2) 8⌈log 2 (sn(G)+1)⌉-6 -1. Since q is constant, queue-number is bounded by a polynomial function of stack-number. ✷

k xy + yx∈E(T ) k yx    ≤ max{d + 1, 3} ≤ d + 1 . (10)
Colour all the edges and nodes of T red. Define λ s as in Lemma 22. That is, λ s is the maximum, taken over all nodes x ∈ V (T ), of

s x + xy∈E(T ) k xy + yx∈E(T ) k yx . (11)
Since every node x ∈ V (T ) has s x = 0, [START_REF] Brandenburg | Proc. International Symp. on Graph Drawing (GD '95)[END_REF]

Mixed Layouts

Theorem 11. For all integers s ≥ 1 and q ≥ 1, every graph G has an s-stack q-queue subdivision with 4⌈log (s+q) q sn(G)⌉ division vertices per edge.

Proof: Apply Lemma 21 with d 1 = s + q, d 2 = q, h = 2⌈log (s+q)q sn(G)⌉, and T a complete (d 1 , d 2 )ary tree of height h. Then G has a subdivision D with 4⌈log (s+q) q sn(G)⌉ division vertices per edge, and D has a simple (1, T )-layout where max x∈V (T ) {s x } ≤ 1 and where every node v ∈ V (T ) at even depth has deg + (v) ≤ s + q and every node v ∈ V (T ) at odd depth has deg + (v) ≤ q. Colour the edges of T as follows. For each non-leaf node v ∈ V (T ) at even depth, colour its outgoing edges red or black so that at most s outgoing edges are red and at most q are black. For nodes v ∈ V (T ) at odd depth, colour the outgoing edges of v black. Clearly this edge colouring is good. By Lemma 17, T has a topological ordering that admits a 1-queue layout of T

[E b ] and a 1-stack layout of T [E r ].
Colour all the vertices of T red. Consequently, every node x in T has q ′ x = 0. (See Lemma 22 to recall the definitions of q ′

x and s ′ x .) For each node x ∈ V (T ), let deg

+ black (x) denote the outdegree of x in T [E b ].
Define λ s and λ q as in Lemma 22. Then

λ q = max x∈V (T )    q ′ x + max y∈V (T ) : y≤σx yz∈E b (T ) : x≤σz k yz    ≤ max x∈V (T )    xv∈E b (T ) k xv    ≤ max x∈V (T ) deg + black (x) ≤ q .
By the properties of the simple (1, T )-layout of D every non-leaf node x of T has s ′ x = 0 and every leaf node x of T has s ′

x ≤ 1. For a node x in T , let deg red (x) denote the degree of x in T [E r ]. Since h is even, the height of T is even and thus all the edges incident to leaves of T are black. For every leaf node x ∈ V (T ) that implies that deg red (x) = 0. Therefore,

λ s = max x∈V (T )    s ′ x + xy∈E r (T ) k xy + yx∈E r (T ) k yx    ≤ max max x∈V (T ) : deg(x)=1 s ′ x , max x∈V (T ) : deg(x) =1 deg red (x) ≤ s .
By Lemma 22, the subdivision D of G has an s-stack q-queue mixed layout. ✷ Theorem 12. For all s ≥ 1 and q ≥ 1, every graph G has an s-stack q-queue subdivision with 2 + 4⌈log (s+q) q qn(G)⌉ division vertices per edge.

Proof: Apply Lemma 21 with d 1 = s + q, d 2 = q, h = 2⌈log (s+q)q qn(G)⌉, and T a tree obtained from a complete (d 1 , d 2 )-ary tree of height h by subdividing each leaf-edge once. The height of T is h + 1 and all of its leaves are at depth h + 1. Then G has a subdivision D with 2 + 4⌈log (s+q) q qn(G)⌉ division vertices per edge, and D has a simple (1, T )-layout in which every non-leaf node x ∈ V (T ) has q x = 0, and every leaf node x ∈ V (T ) has q x ≤ 1.

Colour the edges of T as follows. For each node x ∈ V (T ) at odd depth, colour all its outgoing edges black. For each node x ∈ V (T ) at even depth, if depth(x) < h colour each of its outgoing edges red or black such that s are red and q are black, otherwise, depth(x) = h, colour its only outgoing edge red. Clearly this edge colouring of T is good. Thus by Lemma 17, T has a topological vertex ordering, such that the black edges form a queue, and the red edges form a stack.

Colour all the vertices of T black. Consequently, every node x ∈ V (T ) has s ′ x = 0. (See Lemma 22 to recall the definitions of q ′

x and s ′ x ). For each node x ∈ V (T ), let deg red (x) denote the degree of x in T [E r ]. Define λ s and λ q as in Lemma 22. Then

λ s = max x∈V (T )    s ′ x + xy∈E r (T ) k xy + yx∈E r (T ) k yx    ≤ max x∈V (T ) {deg red (x)} ≤ s .
By the properties of the simple (1, T )-layout of D every non-leaf node x of T has q ′ x = 0 and every leaf node x of T has q ′

x ≤ 1. By construction, the edges incident to leaves of T are red. Thus every leaf node x ∈ V (T ) has degree zero in T [E b ]. Now λ q is the maximum, taken over all nodes x ∈ V (T ), of

q ′ x + max y∈V (T ) : y≤σx yz∈E b (T ) : x≤σz k yz . (12)
Since nodes of T appear in σ according to nondecreasing depth, for each node x ∈ V (T ) at depth i, the summation in ( 12) may be nonzero only for nodes y ∈ V (T ) at depth i -1 and i. Since the nodes at depth h and h + 1 have outdegrees zero in T [E b ], for leaf nodes x, (12) is 1 + 0 = 1. Since the nodes at depth less than h have outdegrees q in T [E b ], for non-leaf nodes x, (12) is 0 + max{q, 0} = q. Since q ≥ 1, by Lemma 22, the subdivision D of G has an s-stack q-queue mixed layout. ✷ Theorems 11 and 12 with s = 1 and q = 1 imply the following. Since the stack-number of a proper minor-closed graph family is bounded [START_REF] Blankenship | Book Embeddings of Graphs[END_REF][START_REF] Oporowski | Book embeddings of graphs and minorclosed classes[END_REF], Corollary 2 implies that every graph from such a family has a 1-stack 1-queue subdivision with a bounded number of division vertices per edge.

Track Layouts

In this section we consider layouts of subdivisions on few tracks. We will need the following lemma for wrapping a track layout from our companion paper [START_REF] Vida Dujmovi | Track layouts of graphs[END_REF].

Lemma 28. [28]

Let {V i,j : i ≥ 0, 1 ≤ j ≤ b i } be a (k, t)-track layout of a graph G with maximum partial span s (for some irrelevant value t). For each 0 ≤ α ≤ s, let t α = max{b i : i ≡ α (mod s + 1)}.

For each 0 ≤ α ≤ 2s, let t ′ α = max{b i : i ≡ α (mod 2s + 1)}. Then (a) tn 2k (G) ≤ s α=0 t α , and (b) tn k (G) ≤ 2s α=0 t ′ α .
The special case of Lemma 28 with b i = 1 (for all i ≥ 0) will be useful.

Lemma 29. [28]

Let G be a (k, t)-track graph with maximum span s. Then (a) tn 2k (G) ≤ s + 1, and

(b) tn k (G) ≤ 2s + 1.
First we consider layouts of subdivisions on two tracks.

Lemma 30.

For every graph G, the subdivision G ′′′ has 2-track thickness θ 2 (G ′′′ ) ≤ 1 + 2⌈ qn(G)⌉. For each intrabag edge vw ∈ E(D 0 ) mapped to a leaf node x ∈ E(T ) such that v < x w in the (1, T )-layout, place the division vertex a vw incident to v in the bag H ax , place the middle division vertex b vw in the bag H bx , and place the division vertex c vw incident to w in the bag H cx . Since the intrabag edges mapped to x in the (1, T )layout of D 0 induce a 1-queue layout, we can order the division vertices in H ax , H bx and H cx by the queue order of the edges they subdivide. As in Lemma 4(c), there is no X-crossing in the resulting layout. Thus we have an H-track layout of D. Now create a track layout of H indexed by

{(i, j) : 0 ≤ i ≤ 3h, 1 ≤ j ≤ d} ∪ {(3h + 1, 1)} .
Nodes are ordered in the obvious way so that there are no X-crossings, as illustrated in Figure 11. Firstly, consider a node x ∈ V (H) that corresponds to a node of T 0 at depth i ≤ h -2 in T 0 . Recall that the first d -1 outgoing edges of x in T 0 are subdivided three times, and the rightmost outgoing edge in T 0 is subdivided twice. Denote the d outgoing paths at x in H by

(x, α 1 , β 1 , γ 1 ), (x, α 2 , β 2 , γ 2 ), . . . , (x, α d-1 , β d-1 , γ d-1 ), (x, β d , γ d ) .
Position x in track (3i, 1). For each 1 ≤ j ≤ d -1, position α j in track (3i, j + 1). For each 1 ≤ j ≤ d, position β j in track (3i + 1, 1), and position γ j in track (3i + 2, 1). Now consider a node x ∈ V (H) that corresponds to a node of T 0 at depth h -1 in T 0 . Recall that the first d -1 outgoing edges of x in T 0 are subdivided twice, and the rightmost outgoing edge in T 0 is Position x in track (3h -3, 1). Position each node α j , 1 ≤ j ≤ d -1, in track (3h -3, j + 1). Position each node β j , 1 ≤ j ≤ d, in track (3h -2, 1). Finally consider a node x ∈ V (H) that corresponds to a leaf node of T 0 (at depth h in T 0 ). Position x in track (3h -1, 1), position a x in track (3h, 1), position b x in track (3h + 1, 1), and position c x in track (3h, 2). Now wrap the track layout of H using Lemma 28(b) with k = 1. The partial span s = 1, so we are wrapping modulo 3 = 2s + 1. Observe that the track layout of H is indexed by: (i, j) : i ≡ 0 (mod 3), 0 ≤ i ≤ 3h, 1 ≤ j ≤ d ∪ (i, 1) : i ≡ 1 (mod 3), 0 ≤ i ≤ 3h + 1 ∪ (i, 1) : i ≡ 2 (mod 3) 0 ≤ i ≤ 3h .

(0, 1) →A 1 (0, 2) →A 2 (0, d) →A d (1, 1) → B (2, 1) → C (3, 1) →A 1 (3, 2) →A 2 (3, d) →A d (4, 1) → B (5, 1) → C (6, 1) →A 1 (3h -3, 1) →A 1 (3h -3, 2) →A 2 (3h -3, d) →A d (3h -2, 1) → B (3h -1, 1) → C (3h, 1) →A 1 (3h, 2) →A 2 (3h + 1, 1) → B ✁ ✁ ✁ ✂ ✂ ✂ ✄ ☎✄ ☎✄ ✆ ☎✆ ☎✆ ✝ ✞✝ ☎✝ ✟ ✟ ✟ ✠ ✞✠ ☎✠ ✡ ☎✡ ☎✡ ☛ ☎☛ ✞☛ ☞ ☞ ☞ ✌ ☎✌ ☎✌ ✍ ☎✍ ☎✍ ✎ ☎✎ ✞✎ ✏ ✏ ✏ ✑ ✑ ✑ ✒ ✒ ✒ ✓ ✓ ✓ ✔ ✔ ✔ ✕ ✕ ✕ ✖ ✖ ✖ ✗ ✗ ✗ ✘ ✘ ✘ α 1 β 1 γ 1 α d-1 β d-1 γ d-1 β d γ d
Thus in Lemma 28(b), we have t ′ 0 = d, t ′ 1 = 1, and t ′ 2 = 1. Thus H has a (d + 2)-track layout. In Figure 11 we indicate the new track assignment by A 1 , . . . , A d , B, C, where for each 0 ≤ i ≤ h, the tracks (3i, j) are mapped A j , the track (3i + 1, 1) is mapped to B, and the track (3i + 2, 1) is mapped to C. Note that for i = 3h we use the assumption that d ≥ 2.

It is easily seen that in the (d + 2)-track layout of H, every node has at most one neighbour on any other track. Thus replacing each node x in the track layout of H by H x , we obtain a (d + 2)-track layout of D, as in Lemma 24. ✷ Note that the bound on the number of division vertices per edge in Theorem 16 can be slightly improved, at the expense of D no longer being bipartite. We will need D to be bipartite in Section 5.

The following result proves that in each of Theorems 14, 15 and 16, the bound on the number of division vertices per edge is within a constant factor of optimal for all graphs.

Planar Mixed Layouts

Since the stack-number of planar graphs is at most four [START_REF] Mihalis Yannakakis | Embedding planar graphs in four pages[END_REF], Theorem 13 implies that every planar graph has a 1-stack 1-queue subdivision with eight division vertices per edge. Although asymptotically much weaker than Theorem 11, the following result gives a better bound on the number of division vertices per edge for graphs with small stack-number. Change the root of T from r to one of the two leaves of T and redirect the edges accordingly. Now every node in T has at most one outgoing edge. Colour all the edges of T black and all the nodes of T red. Since all the edges are black, by Lemma 17, T has a topological ordering σ that admits a 1-queue layout of T . Furthermore, since there are no red edges in T , This concludes the proof ✷ Similar bounds can be be obtained for the number of division vertices per edge in a 1-stack 1-queue subdivision of a graph with small stack-number (see [START_REF] Vida | On linear layouts of graphs[END_REF]). Lemma 34 provides a partial solution to the conjecture of Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF] that every planar graph has a 1-stack 1-queue mixed layout.

Three-Dimensional Polyline Drawings

Track layouts have previously been used to produce three-dimensional drawings with small volume. The principle idea in these constructions is to position the vertices in a single track so that they have the same Xand Y -coordinates. That is, each track is positioned on a vertical 'rod'. Since there are no X-crossings in the track layout, no edges between the same pair of tracks can cross. Theorem 23. [START_REF] Vida Dujmovi | Layout of graphs with bounded treewidth[END_REF][START_REF] Vida | Three-dimensional grid drawings with sub-quadratic volume[END_REF] Let G be a c-colourable t-track graph. Then Proof: Let σ = (v 1 , v 2 , . . . , v n ) be the vertex ordering in a q-queue layout of G. Let {E ℓ : 1 ≤ ℓ ≤ q} be the queues. Order the edges in each queue E ℓ according to the queue order (see Eq. ( 1)). Denote by (L(e), X(e), Y (e), R(e)) the path replacing e in G ′′ , where L(e) < σ R(e). Put each vertex v i at (0, 0, i). If e is the j-th edge in the ordering of E ℓ , put the division vertices X(e) at (1, 2ℓ, j) and Y (e) at (1, 2ℓ + 1, j). Observe that the projection of the drawing onto the XY -plane is planar. Thus the only possible crossings occur between edges contained in a plane parallel with the Z-axis. Thus an X-crossing could only occur between pairs of edges {L(e)X(e), L(f )X(f )}, {X(e)Y (e), X(f )Y (f )}, or {Y (e)R(e), Y (f )R(f )}, where e and f are in a single queue E ℓ . Suppose e < ℓ f . Then the Zcoordinates satisfy: Z(L(e)) ≤ Z(L(f )), Z(R(e)) ≤ Z(R(f )), Z(X(e)) < Z(X(f )), and Z(Y (e)) < Z(Y (f )). Thus there is no crossing. The drawing is at most 2 × 2q × (2n -3) since each queue has at most 2n -3 edges [START_REF] Vida | On linear layouts of graphs[END_REF][START_REF] Heath | Laying out graphs using queues[END_REF][START_REF] Pemmaraju | Exploring the Powers of Stacks and Queues via Graph Layouts[END_REF]. The volume is at most 8qn, which is O(n √ m) [START_REF] Vida | On linear layouts of graphs[END_REF][START_REF] Heath | Laying out graphs using queues[END_REF][START_REF] Shi | On crossing sets, disjoint sets, and pagenumber[END_REF]. ✷

Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF] observed that the complete graph K n has a ⌊ n 2 ⌋-queue layout. Thus Theorem 26 gives a 2 × n × (2n -3) polyline drawing of K n with two bends per edge. Independent of this research, Dyck et al. [START_REF] Dyck | Drawing K n in three dimensions with two bends per edge[END_REF] also proved that K n has a 3D 2-bend drawing with O(n 2 ) volume.

Theorem 27. Let G be a q-queue graph with n vertices and m edges. For every ǫ > 0, G has a 2 × ⌈q ǫ ⌉ + 2 × n + (8 1 ǫ + 1)m polyline drawing with at most 8⌈ 1 ǫ ⌉ + 1 bends per edge. The volume is O(q ǫ (n + m ǫ )). For constant ǫ there are O(1) bends per edge and the volume is O(q ǫ (n + m)), which is in O(n ǫ (n + m)).

  The number of vertices and edges of G are respectively denoted by n = |V (G)| and m = |E(G)|. The subgraph of G induced by a set of vertices A ⊆ V (G) is denoted by G[A]. For all A, B ⊆ V (G) with A ∩ B = ∅, we denote by G[A, B] the bipartite subgraph of G with vertex set A ∪ B and edge set {vw ∈ E(G) : v ∈ A, w ∈ B}. The spanning subgraph of G induced by a set of edges S ⊆ E(G) is denoted by G[S].

Fig. 1 :

 1 Fig. 1: Layouts of K6: (a) 3-stack, (b) 3-queue.

Theorem 1 . [ 7 , 39 , 70 , 73 ]

 17397073 Every graph has a 3-stack subdivision.

for k = 1 . 1 .Fig. 2 :

 112 Fig. 2: Layouts of a caterpillar: (a) 2-track, (b) 1-queue, (c) 1-stack.

  the vertices of G are on one track and the division vertices are on the other track. Let σ be the ordering of the original vertices of G on the first track, and let π be the ordering of the division vertices on the second track. Let 1 ≤ col(e) ≤ k be the colour assigned to each edge e of G ′ . Consider V (G) to be ordered by σ. Partition the edges of G into queues as follows. For each edge vw ∈ E(G) subdivided by vertex x in G ′ , let queue(vw) = {col(vx), col(wx)}. We now prove that this defines a queue layout of G. Say vw is nested inside ab in σ. Without loss of generality a < σ v < σ w < σ b. Let vw be divided by x in G ′ , and let ab be divided by c in G ′ . First suppose that x < π c in the second track. Then each of xw and xv form an X-crossing with ac. Thus col(xw) = col(ac) and col(xv) = col(ac). Hence queue(vw) = queue(ab). Now suppose c < π x in the second track. Then bc forms an X-crossing with each of xw and xv. Thus col(bc) = col(xw) and col(bc) = col(xv). Hence queue(vw) = queue(ab). The number of queues in the queue layout of G is k

Fig. 3 :

 3 Fig. 3: Illustration for Lemma 4(c).

Fig. 4 :

 4 Fig. 4: 1-queue layout of a complete binary tree.

Fig. 5 :

 5 Fig. 5: 1-stack layout of a complete binary tree.

Fig. 7 :

 7 Fig. 7: Illustration for Lemma 20. Given (a) a labelled tree T and (b) a 4-stack layout of G (that is also a 4-queue layout), the algorithm produces a (1, T )-layout of a subdivision of G with (c) sx ≤ l(x) or (d) qx ≤ l(x).

Theorem 4 .

 4 is d+d = 2 d. For the root node r, (6) is 0+d = d. Thus λ q = 2 d. By Lemma 22, G ′′ has a 2 d-queue layout. ✷ For every integer d ≥ 2, every graph G has a d-queue subdivision with 2⌈log d qn(G)⌉ + 1 division vertices per edge. Proof: Let T 0 be the complete d-ary tree of height h = ⌈log d qn(G)⌉. By Lemma 21 with d 1 = d 2 = d, G has a subdivision D 0 with 2h division vertices per edge, such that D 0 has a simple (1, T 0 )-layout in which every non-leaf node x ∈ V (T 0 ) has q x = 0, and every leaf node x ∈ V (T 0 ) has q x ≤ 1. Let D be subdivision of G obtained from D 0 by subdividing each intrabag edge (in the (1, T 0 )-layout of D 0 ) once. Clearly D has 2⌈log d qn(G)⌉ + 1 division vertices per edge of G. By Lemma 25 with c = 1 applied to D 0 , there is a tree T such that D has a (2, T )-track layout in which every node x ∈ V (T ) has xy∈E(T )

Fig. 8 :

 8 Fig. 8: A 2-queue subdivision of an 8-queue graph.

Corollary 1 .Theorem 7 . 9 )Fig. 9 :

 1799 Fig. 9: 3-stack subdivision of a 16-stack graph.

Theorem 9 .

 9 For every integer s ≥ 3, every graph G has an s-stack subdivision with 1+2⌈log s-1 qn(G)⌉ division vertices per edge. Proof: Let d = s -1. Apply Lemma 21 with T 0 the complete d-ary tree of height h = ⌈log d qn(G)⌉.Then G has a subdivision D 0 with 2⌈log d qn(G)⌉ division vertices per edge such that D 0 has a simple (1, T 0 )-layout in which every non-leaf node x ∈ V (T ) has s x = 0, and every leaf node has x ∈ V (T ) has q x ≤ 1. Let D be the subdivision of G obtained by subdividing each intrabag edge of D 0 once. Thus D has 1 + 2⌈log s-1 qn(G)⌉ division vertices per edge of G. By Lemma 25 with c = 1, there exists a tree T such that D has a (2, T )-track layout, where max

Fig. 10 :

 10 Fig. 10: Track layout of a subdivision of K8 before wrapping. D of G in which every edge of G has an odd number of division vertices in D. Thus D is bipartite, and has at most 8⌈log d qn(G)⌉ + 1 division vertices per edge.Create a (1, H)-layout of D from the simple (1, T )-layout of D 0 as follows. For each intrabag edge vw ∈ E(D 0 ) mapped to a leaf node x ∈ E(T ) such that v < x w in the (1, T )-layout, place the division vertex a vw incident to v in the bag H ax , place the middle division vertex b vw in the bag H bx , and place the division vertex c vw incident to w in the bag H cx . Since the intrabag edges mapped to x in the (1, T )layout of D 0 induce a 1-queue layout, we can order the division vertices in H ax , H bx and H cx by the queue order of the edges they subdivide. As in Lemma 4(c), there is no X-crossing in the resulting layout. Thus we have an H-track layout of D. Now create a track layout of H indexed by

Fig. 11 :

 11 Fig. 11: Track layout of H. subdivided once. Denote the d outgoing paths at x in H by (x, α 1 , β 1 ), (x, α 2 , β 2 ), . . . , (x, α d-1 , β d-1 ), (x, β d ) .

Lemma 33 .

 33 For every integer s ≥ 1, every graph G has a s-stack 1-queue subdivision with at most ⌈sn(G)/s⌉ division vertices.Proof: Let k = ⌈sn(G)/s⌉. Let h = ⌊ k 2 ⌋.Let T be the path on 2h edges rooted at the 'middle' vertex r. Thus T has height h. Label each node x ∈ V (T ) by l(x) = s. Then x l(x) = (2h + 1)s = (2⌊ k 2 ⌋ + 1)s ≥ ks = ⌈sn(G)/s⌉s ≥ sn(G). By Lemma 20, G has a subdivision D with at most 2h ≤ k division vertices per edge, and D has a (1, T )-layout such that s x ≤ s for all nodes x ∈ V (T ).

k xv ≤ 1 .(Lemma 34 .

 134 Since there are no black nodes and since every node has at most one black outgoing edge max See Lemma 22 to recall the definitions of q ′x and s ′ x ). Therefore by Lemma 22, D has an s-stack 1-queue mixed layout. ✷ By Lemma 33 with s = 1 and since planar graphs have 4-stack layouts[START_REF] Mihalis Yannakakis | Embedding planar graphs in four pages[END_REF] we have: Every planar graph has a 1-stack 1-queue subdivision with four division vertices per edge.

Proof:Theorem 28 .Corollary 3 .

 283 Let d = ⌈q ǫ ⌉. By Theorem 16, G has a bipartite subdivision D with at most 8⌈log d q⌉ + 1 division vertices per edge such that the track-number tn(D) ≤ d + 2. Now log d q ≤ 1 ǫ . Thus D has at most 8⌈ 1 ǫ ⌉ + 1 division vertices per edge, and tn(D) ≤ ⌈q ǫ ⌉ + 2. The number of vertices of D is at most n + (8⌈ 1 ǫ ⌉ + 1)m. By Lemma 37, D has a 2 × (⌈q ǫ ⌉ + 2) × (n + (8⌈ 1 ǫ ⌉ + 1)m) straight-line drawing, which is the desired 3D polyline drawing of G. The other claims immediately follow since q ≤ n. ✷ Every q-queue graph G with n vertices and m edges has a 2 × 2 × n + (8 ⌈log 2 q⌉ + 1)m polyline drawing on a rectangular prism. There are O(log q) bends per edge, and the volume is O(n + m log q), which is in O(n + m log n). Proof: By Theorem 16, G has a 4-track subdivision D with at most 8⌈log 2 q⌉ + 1 division vertices per edge. The number of vertices of D is at most n + (8⌈log 2 q⌉ + 1)m. By Lemma 36, D has a 2 × 2 × (n + (8⌈log 2 q⌉ + 1)m) straight-line drawing, which is the desired polyline drawing of G. The volume is O(n + m log n) since q ≤ n. ✷ Since the queue-number of an n-vertex graph is at most n we have the following corollary of Theorem 28. Every graph with n vertices and m edges has a polyline drawing with O(n + m log n) volume and O(log n) bends per edge. ✷

  Layouts of a subdivision of a graph G.

	Tab. 1: graph type of layout	# division vertices per edge reference
	arbitrary arbitrary planar	s-stack (s ≥ 3) s-stack (s ≥ 3) 2-stack	O(log s-1 sn(G)) O(log s-1 qn(G)) 1	Theorem 7 Theorem 9 [49, 66]; Lemma 31
	arbitrary

  has at most one neighbour in each track V j , 1 ≤ j ≤ i -1.Then replacing each node x in the t-track layout of H by (H x , < x ) from the (k, H)-track layout of G, gives a (p, t)-track layout of G. Define an edge colouring of G as follows. For each node x of T in track V i , and for each ℓ, i < ℓ ≤ t, consider the set of edges E ℓ incident to x that have their other endpoint in V ℓ . Colour the edges of G that are mapped to the edges of E ℓ with p colours such that any two edges e 1 , e 2 ∈ E(G) receive the same colour if and only if they are mapped to the same edge xy ∈ E ℓ and they belong to the same colour class in the (k, H)-layout of G. This is possible with at most p colours by (

				Let G be a graph with a
	(k, H)-track layout. Let
	p = max x∈V (H)	max 1≤ℓ≤t	xy∈E(H) : track(y)=ℓ k xy .	(4)

Proof:

  is at most d + 1 by[START_REF] Bose | The maximum number of edges in a three-dimensional grid-drawing[END_REF]. Thus λ s ≤ d + 1 = s. By Lemma 16, T has a 1-stack layout, and by Lemma 22, D has a s-stack layout.✷ Theorem 9 has the following implication for Open Problem 1. Conjecture 1 states that there exists a function f , such that for every graph G and every s-stack subdivision H of G with at most one division vertex per edge, we have sn(G) ≤ f (s). Thus there exists a function f * such that for any s-stack subdivision of a graph G with k division vertices per edge, G has a f * (s, k)-stack layout. By Theorem 9, every graph G has a 3-stack subdivision with 1 + 2⌈log 2 qn(G)⌉ division vertices per edge. Thus sn(G) ≤ f * (3, 1 + 2⌈log qn(G)⌉), and stack-number is bounded by queue-number. ✷

	Theorem 10. If Conjecture 1 is true then stack-number is bounded by queue-number.

Proof:

Acknowledgements

Thanks to Stefan Langerman for stimulating discussions on 3D polyline drawings. Thanks to Franz Brandenburg and Ulrik Brandes for pointing out the connection to double-ended queues. Thanks to Ferran Hurtado and Prosenjit Bose for graciously hosting the second author.

05C62 (graph representations) † Research of V. Dujmović is supported by NSERC. Research of D. Wood is supported by the Government of Spain grant MEC SB2003-0270.

Proof: Let d = ⌈ qn(G)⌉. Let T 0 be the complete d-ary tree of height 1; that is, the d-ary star. By Lemma 21, G ′′ has a simple (1, T 0 )-layout in which the root node r has deg + (r) = d and q r = 0, and every leaf node x ∈ V (T 0 ) has q x ≤ ⌈qn(G)/d⌉ ≤ d. Let T be the tree obtained by subdividing each edge of T 0 . Let r be the root node of T . By Lemma 25 with c = d, the subdivision G ′′′ has a (d + 1, T )track layout in which k rx = 1 for every edge rx incident to the root, and k xy = d + 1 for every leaf-edge xy. Consider the (2, 2)-track layout of T with the root preceding the leaf nodes on the first track, and the remaining nodes on the second track. Replace each node x of T by T x . We obtain a (2d + 1, 2)-track layout of G ′′′ . ✷ Proof: Let T 0 be the complete d-ary tree of height h = ⌈log d qn(G)⌉. Let T be the subdivision of T 0 obtained as follows. For each node x ∈ V (T 0 ) at depth at most h -2, subdivide its rightmost outgoing edge twice, and subdivide the remaining d -1 outgoing edges three times. For each non-leaf node x ∈ V (T 0 ) that is incident to a leaf-edge, subdivide its rightmost outgoing edge once, and subdivide the remaining d -1 outgoing edges twice. The resulting tree T has height h + 3h -1 = 4⌈log d qn(G)⌉ -1. By Lemma 21, G has a subdivision D 0 with at most 8⌈log d qn(G)⌉ -2 division vertices per edge and a simple (1, T )-layout, such that every non-leaf node x ∈ V (T ) has q x = 0, and every leaf node x ∈ V (T ) has q x ≤ 1. Moreover, every edge of G has an even number of division vertices in D.

Let H the graph obtained from T by adding a 4-cycle (x, a x , b x , c x ) to each leaf node x ∈ V (T ), as illustrated in Figure 11. Now subdivide every intrabag edge vw of D 0 three times. We obtain a subdivision Theorem 17. In every (k, t)-track subdivision D of a graph G there is an edge with at least Proof: By Theorem 1 with d = 2 every graph has a 3-stack subdivision. The 2-stack graphs are precisely the subgraphs of planar Hamiltonian graphs [START_REF] Bernhart | The book thickness of a graph[END_REF]. Thus a non-planar graph does not have a 2-stack subdivision. Many authors [START_REF] Di | Curve-constrained drawings of planar graphs[END_REF][START_REF] Wiese | Embedding vertices at points: Few bends suffice for planar graphs[END_REF][START_REF] Wenger | Embedding planar graphs at fixed vertex locations[END_REF] have observed that every planar graph has a subdivision that is a subgraph of a planar Hamiltonian graph (see Lemma 31 below), and hence has a 2-stack layout. The 1-stack graphs are precisely the outerplanar graphs [START_REF] Bernhart | The book thickness of a graph[END_REF]. Thus, for any outerplanar graph, the graph itself is a 1-stack subdivision. Conversely, if a subdivision of a graph G is outerplanar then so is G. Thus only the outerplanar graphs have 1-stack subdivisions. ✷

We now consider how many division vertices per edge are needed in a 2-stack subdivision of any planar graph. Pach and Wenger [START_REF] Wenger | Embedding planar graphs at fixed vertex locations[END_REF] proved that the subdivision of a planar graph with two division vertices per edge is the subgraph of a Hamiltonian planar graph, and hence has a 2-stack layout. Kaufmann and Wiese [START_REF] Wiese | Embedding vertices at points: Few bends suffice for planar graphs[END_REF] and Giacomo et al. [START_REF] Di | Curve-constrained drawings of planar graphs[END_REF] improved this result by showing that the subdivision G ′ of a planar graph G with one division vertex per edge is the subgraph of a Hamiltonian planar graph, and hence has a 2stack layout. (Note that Pach and Wenger [START_REF] Wenger | Embedding planar graphs at fixed vertex locations[END_REF] were more interested in the total number of vertices in the Hamiltonian supergraph rather than the number of division vertices per edge. Giacomo et al. [START_REF] Di | Curve-constrained drawings of planar graphs[END_REF] also prove that the division vertex x of each edge vw is between v and w in the 2-stack layout.) Here we give a new proof of the above result in [START_REF] Di | Curve-constrained drawings of planar graphs[END_REF][START_REF] Wiese | Embedding vertices at points: Few bends suffice for planar graphs[END_REF], with the additional property that the Hamiltonian supergraph is bipartite.

Lemma 31. For every planar graph G, the subdivision G ′ of G with one division vertex per edge is the subgraph of a bipartite Hamiltonian planar graph, and hence has a 2-stack layout.

Proof: Without loss of generality G is a triangulation. Otherwise we can add edges to G so that every face is a 3-cycle. Let V = V (G). Now subdivide every edge once. Let X be the set of these division vertices. Finally add a single vertex to each face adjacent to the six vertices on that face. Let Y be the set of these vertices. We obtain a planar triangulation H. Observe that {V, X, Y } is a vertex 3-colouring of H. Thus every triangle of H contains one vertex from each of V , X and Y . Every such triangle forms a face of H. Therefore every triangle in H is a face, and H has no separating triangles. Since H is a triangulation, by the classical result of Whitney [START_REF] Whitney | A theorem on graphs[END_REF], H has a Hamiltonian cycle C.

The subgraph of H induced by V ∪ X is G ′ . Thus H and G ′ are 2-stack graphs. We now construct a bipartite Hamiltonian planar graph W from H such that G ′ is a subgraph of W . Consider a face f of G ′ . Let x be the vertex adjacent to every vertex of f in H. Exactly two edges incident to x are in C. Say xv, xw ∈ C, where v, w ∈ f . Delete all the edges incident to x except xv and xw. Clearly the resulting graph remains Hamiltonian. In the case that the distance from v to w along the boundary of f is odd, subdivide the edge xv. The resulting graph W is clearly Hamiltonian. It is easily verified that each face of W is an even cycle. Thus W is bipartite. ✷

Planar Queue and Track Layouts

Felsner et al. [START_REF] Stefan Felsner | Straight-line drawings on restricted integer grids in two and three dimensions[END_REF] asked the following question.

Open Problem 3. [44] Does every n-vertex planar graph have a 3D straight-line drawing with O(n) volume?

By Theorem 23 below, this question has an affirmative answer if planar graphs have bounded tracknumber. Whether planar graphs have bounded track-number is an open problem due to Hubert de Fraysseix [private communication, 2000], and since queue-number is tied to track-number [START_REF] Vida Dujmovi | Track layouts of graphs[END_REF], is equivalent to the following open problem due to Heath et al. [START_REF] Heath | Comparing queues and stacks as mechanisms for laying out graphs[END_REF][START_REF] Heath | Laying out graphs using queues[END_REF].

Open Problem 4. [56, 57] Do planar graphs have bounded queue-number?

We make the following contribution to the study of this problem, which is analogous to Theorem 8 for arbitrary graphs. Note that the best known upper bound on the queue-number of planar graphs is O( √ n).

Theorem 19. Let F(n) be the family of functions O(1) or O(polylog n). The following are equivalent:

(1) n-vertex planar graphs have queue-number in F(n),

(2) n-vertex bipartite Hamiltonian planar graphs have queue-number in ✷

We now answer the questions discussed at the start of this section in the case of queue and track layouts.

Lemma 32. Every n-vertex planar graph G has a subdivision D such that every edge has at most n -2 division vertices, and D admits an n-track layout with every edge having span one.

Proof: By the classical result of Fáry [START_REF] Án | On straight line representation of planar graphs[END_REF] and Wagner [START_REF] Wagner | Bemerkung zum Vierfarbenproblem[END_REF], G has a straight-line plane drawing. Rotate such a drawing so that every vertex has a unique Y -coordinate. Draw n lines parallel to the X-axis, one through each vertex, and subdivide every edge at the point at which it crosses a line. The subdivision D obtained has at most n -2 division vertices per edge. Now consider each line to be a track. Since there are no crossings in the drawing, there are no X-crossings in the track assignment of D.

The constants in Theorem 23 can be significantly improved in the case of 3-track and 4-track layouts. Here the vertices are positioned on the edges of a triangular or rectangular prism. These models of graph drawing were introduced by Felsner et al. [START_REF] Stefan Felsner | Straight-line drawings on restricted integer grids in two and three dimensions[END_REF].

Then G has a 2×2×n ′ straight-line drawing with the vertices on a triangular prism. In this case, G is necessarily planar.

Proof: Position the i-th vertex in V 1 at (0, 0, i). Position the i-th vertex in V 2 at (1, 0, i). Position the i-th vertex in V 3 at (0, 1, i). Since there is no X-crossing in the track layout, no two edges cross. Since G is embedded in a surface homeomorphic to the sphere, G is planar.

Then G has a 2 × 2 × 2n ′ straight-line drawing with the vertices on a rectangular prism.

Proof: Position the i-th vertex in V 1 at (0, 0, 2i). Position the i-th vertex in V 2 at (1, 0, 2i). Position the i-th vertex in V 3 at (0, 1, 2i). Position the i-th vertex in V 4 at (1, 1, 2i + 1). Clearly the only possible crossing is between edges vw and xy

2 ) for some integer α, and xy intersects L at ( 1 2 , 1 2 , β) for some integer β. Thus vw and xy do not intersect. ✷ Di Giacomo and Meijer [START_REF] Di | Track drawings of graphs with constant queue number[END_REF] proved that a 4-track graph with n vertices has a 2 × 2 × n drawing. When n ′ < n 2 the above construction has less volume. In the case of bipartite graphs, the authors [START_REF] Vida | Three-dimensional grid drawings with sub-quadratic volume[END_REF] gave a simple proof of Theorem 23(b) with improved constants, which we include for completeness. The construction is illustrated in Figure 12.

Proof: Let {T

The drawing is thus 2 × t × max{|A|, |B|}. There is no crossing between edges in G[A i , B j ] and G[A i , B j ] as otherwise there would be an X-crossing in the track layout. Clearly there is no crossing between edges in G[A i , B j ] and G[A i , B k ] for j = k. Suppose there is a crossing between edges in G[A i , B j ] and G[A k , B ℓ ] with i = k and j = ℓ. Without loss of generality i < k. Then the projections of the edges in the XY -plane also cross, and thus ℓ < j. This implies that the projections of the edges in the XZ-plane do not cross, and thus the edges do not cross. ✷ We now prove results for 3D 1-bend drawings.

Theorem 24. Every c-colourable q-queue graph G with n vertices and m edges has a 2 × c(q + 1) × (n + m) polyline drawing with one bend per edge. The volume is 2c(q + 1)(n + m).

Proof:

The subdivision G ′ of G with one division vertex per edge is bipartite and has n + m vertices. By Lemma 4(b), tn(G ′ ) ≤ c(q + 1). Thus by Lemma 37, G ′ has a 2 × c(q + 1) × (n + m) straight-line drawing, which is the desired 3D polyline drawing of G. ✷

The next result applies a construction of Calamoneri and Sterbini [START_REF] Sterbini | 3D straight-line grid drawing of 4-colorable graphs[END_REF].

Theorem 25. Every n-vertex m-edge graph G has an n × m × 2 polyline drawing with one bend per edge.

Proof: Let (v 1 , v 2 , . . . , v n ) be an arbitrary vertex ordering of G. Let (x 1 , x 2 , . . . , x m ) be an arbitrary ordering of the division vertices of G ′ . Place each v i at (i, 0, 0) and each x j at (0, j, 1). Clearly the endpoints of any two disjoint edges of G ′ are not coplanar (see [START_REF] Sterbini | 3D straight-line grid drawing of 4-colorable graphs[END_REF]). Thus no two edges cross, and we have an n × m × 2 straight-line drawing of G ′ , which is a 3D 1-bend drawing of G. ✷

Subsequent to this research, Morin and Wood [START_REF] Morin | Three-dimensional 1-bend graph drawings[END_REF] studied 3D 1-bend drawings. They showed that if the vertices are required to be collinear, then the minimum volume of a 3D 1-bend drawing of any n-vertex graph with cutwidth c is Θ(cn). Moreover, they proved that every graph has a 3D 1-bend drawing with O(n 3 / log 2 n) volume. Now consider 3D 2-bend drawings. For every q-queue graph G, the subdivision G ′′ is obviously 3colourable. Thus by Lemma 4(c) and Theorem 23(b), G has a O(1) × O(q) × O(n + m) polyline drawing with two bends per edge. This result can be improved as follows.

Theorem 26. Every n-vertex m-edge q-queue graph G has a 2 × 2q × (2n -3) polyline drawing with two bends per edge. The volume is at most 8qn ∈ O(n √ m).