Vida Dujmović

Attila Pór
email: attila.por@case.edu

David R Wood
email: wood@cs.mcgill.ca

Track Layouts of Graphs †

Keywords: graph layout, graph drawing, track layout, stack layout, queue layout, book embedding, track-number, queue-number, stack-number, page-number, book-thickness, geometric thickness, three-dimensional graph drawing, acyclic chromatic number Mathematics Subject Classification: 05C62 (graph representations), 05C15 (coloring

A (k,t)-track layout of a graph G consists of a (proper) vertex t-colouring of G, a total order of each vertex colour class, and a (non-proper) edge k-colouring such that between each pair of colour classes no two monochromatic edges cross. This structure has recently arisen in the study of three-dimensional graph drawings. This paper presents the beginnings of a theory of track layouts. First we determine the maximum number of edges in a (k,t)-track layout, and show how to colour the edges given fixed linear orderings of the vertex colour classes. We then describe methods for the manipulation of track layouts. For example, we show how to decrease the number of edge colours in a track layout at the expense of increasing the number of tracks, and vice versa. We then study the relationship between track layouts and other models of graph layout, namely stack and queue layouts, and geometric thickness. One of our principle results is that the queue-number and track-number of a graph are tied, in the sense that one is bounded by a function of the other. As corollaries we prove that acyclic chromatic number is bounded by both queue-number and stack-number. Finally we consider track layouts of planar graphs. While it is an open problem whether planar graphs have bounded track-number, we prove bounds on the track-number of outerplanar graphs, and give the best known lower bound on the track-number of planar graphs.

Introduction

In its simplest form, a track layout of a graph consists of a vertex colouring and a total order on each colour class, such that there is no pair of crossing edges between any two colour classes. The purpose of this paper is to develop the beginnings of a theory of track layouts. Our focus is on methods for the manipulation of track layouts, and the relationship between track layouts and other models of graph layout. We consider undirected, finite, and simple graphs G with vertex set V (G) and edge set E(G). The number of vertices and edges of G are respectively denoted by n = |V (G)| and m = |E(G)|.

A vertex |I|-colouring of a graph G is a partition {V i : i ∈ I} of V (G) such that for every edge vw ∈ E(G), if v ∈ V i and w ∈ V j then i = j. The elements of I are colours, and each set V i is a colour class. The chromatic number of G, denoted by χ(G), is the minimum number k such that G has a vertex k-colouring.

Consider a vertex I-colouring {V i : i ∈ I} of a graph G. Suppose that < i is a total order on each colour class V i . Then each pair (V i , < i ) is a track, and {(V i , < i ) : i ∈ I} is an |I|-track assignment of G. To ease the notation we denote track assignments by {V i : i ∈ I} when the ordering on each colour class is implicit.

An X-crossing in a track assignment consists of two edges vw and xy such that v, x ∈ V i , w, y ∈ V j , 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). 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; that is, edges of the same colour do not form an 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 below). 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). Dujmović et al. [START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF] first introduced track layouts and track-number, although similar structures are implicit in many previous works [START_REF] Stefan Felsner | Straight-line drawings on restricted integer grids in two and three dimensions[END_REF][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][START_REF] Madhavan | Stack and queue number of 2-trees[END_REF].

The graphs that admit 2-track layouts are easily characterised as follows, where a caterpillar is a tree such that deleting the leaves gives a path, as illustrated in Figure 1.

Lemma 1. [37]

A graph has a 2-track layout if and only if it is a forest of caterpillars. Table 1 summarises the known bounds on the track-number. Part of the motivation for studying track layouts is a connection with three-dimensional graph drawings. A three-dimensional straight-line grid drawing of a graph, henceforth called a 3D drawing, is a placement of the vertices at distinct points in Z 3 (called gridpoints), such that the line-segments representing the edges are pairwise non-crossing. That is, distinct edges only intersect at common endpoints, and each edge only intersects a vertex that is an endpoint of that edge. The bounding box of a 3D 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 drawing with volume X • Y • Z. That is, the volume of a 3D

O(h 3/2 n 1/2 )
Dujmović and Wood [START_REF] Vida | Three-dimensional grid drawings with sub-quadratic volume[END_REF] genus γ O(γ 1/2 n 1/2 ) Dujmović and Wood [START_REF] Vida | Three-dimensional grid drawings with sub-quadratic volume[END_REF] tree-width w 3 w • 6 (4 w -3w-1)/9 Dujmović et al. [START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF] tree-width w, max. degree ∆ 72∆w Dujmović et al. [START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF] queue-number k, acyclic chromatic number c c(2k) c-1 Dujmović et al. [START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF]; see Theorem 2 queue-number k 4k • 4 k(2k-1)(4k- [START_REF] Stefan Felsner | Straight-line drawings on restricted integer grids in two and three dimensions[END_REF] drawing is the number of gridpoints in the bounding box. Minimising the volume in 3D drawings is a widely studied problem [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 tree-width[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]. The following general bounds are known for the volume of 3D drawings in terms of the track-number. Other papers to employ track layouts in the production of 3D drawings include [START_REF] Di | Drawing series-parallel graphs on restricted integer 3D grids[END_REF][START_REF] Di | Track drawings of graphs with constant queue number[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]. The purpose of this paper is to present fundamental results in the theory of track layouts. In Section 2.1 we show how to colour the edges of a track assignment to obtain a track layout. In Section 2.2 we answer the extremal question: what is the maximum number of edges in a (k,t)-track layout? Section 3 presents methods for manipulating track layouts. In particular, we show how to 'wrap' a track layout. This process can be used to produce a track layout of a graph given track layouts of its biconnected components. Section 4 studies the tradeoff between the number of tracks and the number of edge colours in a track † A track layout that allows edges between consecutive vertices in a track is called an improper track layout [START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF]. This concept, in the case of three tracks, was introduced by Felsner et al. [START_REF] Stefan Felsner | Straight-line drawings on restricted integer grids in two and three dimensions[END_REF], who proved that every outerplanar graph has an improper 3-track layout. It is easily seen that the tracks can be 'doubled' to obtain a (proper) 6-track layout [START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF]. Lemma 22 improves this bound to 5. Similarly, Di Giacomo and Meijer [START_REF] Di | Track drawings of graphs with constant queue number[END_REF] proved that X-trees have improper 3-track layouts, and Halin graphs have improper 4-track layouts. Thus X-trees have (proper) 6-track layouts, and Halin graphs have (proper) 8-track layouts.

layout. In Sections 5 and 6 we explore the relationship between track layouts and other models of graph layout; in particular, stack and queue layouts in Section 5, and geometric thickness in Section 6. One of our main results is that track-number is tied to queue-number. As corollaries we prove that acyclic chromatic number is bounded by both stack-number and queue-number. In Section 7 we prove bounds on the track-number of outerplanar graphs, and prove the best known lower bound on the track-number of planar graphs. Section 8 concludes with some open problems regarding the computational complexity of recognising (k,t)-track graphs. Note that a number of results in this paper are used to prove results in our companion paper on layouts of graph subdivisions [START_REF] Vida | Layouts of graph subdivisions[END_REF].

Definitions

Before we move on, here are some definitions. The subgraph of a graph G induced by a set of vertices 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(1). A graph parameter α is bounded by a graph parameter β , if there exists a binding function g such that α(G) ≤ g(β(G)) for every graph G. If α is bounded by β and β is bounded by α then α and β are tied. 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.

A ⊆ V (G) is denoted by G[A]. For all disjoint A, B ⊆ V (G),
A vertex ordering of an n-vertex graph G is a bijection σ : V (G) → {1, 2, . . . , n}. We write v < σ w to mean that σ(v) < σ(w). One can thus view < σ as a total order on V (G). We say G (or V (G)) is ordered by < σ . 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. These notions extend to subsets of vertices in the natural way. 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 .

Basics

Fixed Track Assignment

We now show how to colour the edges in a track assignment so that no monochromatic edges form an X-crossing. A set S of k edges in a track assignment A is called a crossing k-tuple if each pair of edges in S form an X-crossing in A. E(G[A,B]). Two edges are incomparable under if and only if they form an Xcrossing. Thus an antichain in (that is, a set of pairwise incomparable elements) is a crossing tuple. By assumption, has no antichain of size k + 1. By Dilworth's Theorem [START_REF] Dilworth | A decomposition theorem for partially ordered sets[END_REF], E(G[A, B]) can be partitioned into k chains. A chain in is a set of edges of G[A, B], no two of which form an X-crossing. Thus the partition into k chains defines the desired edge colouring of a (k,t)-track layout.

Note that Lemma 2 essentially says that permutation graphs are perfect (see [START_REF] Branst | Graph classes: a survey[END_REF]).

Extremal Questions

Consider the maximum number of edges in a track layout. It follows from Lemma 1 that an n-vertex 2-track graph has at most n -1 edges, which generalises to (k, 2)-track graphs as follows.

Lemma 3. Every (k, 2)-track graph with n ≥ 1 vertices has at most k(n -1) edges. Moreover, if n ≥ 2k -1, then there are at most k(nk) edges. Conversely, for all k ≥ 1 and n 1 , n 2 ≥ k, there exists a (k, 2)-track layout with k(n 1 + n 2k) edges, and with n 1 vertices in the first track and n 2 vertices in the second track.

Proof. First we prove the upper bounds. Let (v 1 , v 2 , . . . , v n 1 ) and (w 1 , w 2 , . . . , w n 2 ) be the tracks, where n = n 1 + n 2 . For each edge v i w j , let λ(v i w j ) = i + j. Observe that 2 ≤ λ(v i w j ) ≤ n. Thus there are at most n -1 possible λ values. If distinct edges e and f have λ(e) = λ( f ) then e and f form an X-crossing. Thus at most k edges have the same λ value. Hence the number of edges is at most k(n -1). Now suppose that n ≥ 2k -1. For all 1 ≤ i ≤ k -1, at most i edges e have λ(e) = i + 1 (≤ k), and at most i edges e have λ(e) = n + 1i (≥ k + 1). Thus the number of edges is at most

2 k-1 ∑ i=1 i + n -1 -2(k -1) k = k n -k .
Now we prove the lower bound. Let A = (v 1 , v 2 , . . . , v n 1 ) and B = (w 1 , w 2 , . . . , w n 2 ). Construct a graph G with V (G) = A ∪ B. For each 1 ≤ ℓ ≤ k, let E ℓ be the set of edges

v ℓ w j : 1 ≤ j ≤ n 2 + 1 -ℓ [ v i w n 2 +1-ℓ : ℓ + 1 ≤ i ≤ n 1 . Observe that E ℓ 1 ∩ E ℓ 2 = / 0 for distinct ℓ 1 and ℓ 2 . Let E(G) = S ℓ E ℓ .
Clearly no two edges in each E ℓ form an X-crossing, as illustrated in Figure 2. Thus G has a (k, 2)-track layout. The number of edges is

k ∑ ℓ=1 (n 2 + 1 -ℓ) + (n 1 -ℓ) = k(n 1 + n 2 ) - k ∑ ℓ=1 (2ℓ -1) = k(n 1 + n 2 -k) .
Note that the condition n ≥ 2k -1 in Lemma 3 is implied if in fact there is a crossing k-tuple. Lemma Proof. First we prove the upper bounds. Let n i be the number of vertices in the i-th track. Let m i, j be the number of edges between the i-th and j-th tracks. By Lemma 3, m i, j ≤ k(n i + n j -1). Hence the total number of edges is at most

∑ 1≤i< j≤t k(n i + n j -1) = k ∑ 1≤i< j≤t (n i + n j ) -t 2 = k (t -1)n -t 2 .
Now suppose that every pair of tracks has at least 2k -1 vertices. By Lemma 3, m i, j ≤ k(n i + n jk). Hence the total number of edges is at most

∑ 1≤i< j≤t k(n i + n j -k) = k ∑ 1≤i< j≤t (n i + n j ) -k t 2 = k (t -1)n -k t 2 .
Now we prove the lower bound. Given any k ≥ 1, t ≥ 2 and n ≥ kt, arbitrarily partition n into t integers n = n 1 + n 2 + • • • + n t with each n i ≥ k. Construct a (k,t)-track layout with n i vertices in the i-th track, and k(n i + n jk) edges between the i-th and j-th tracks, as in Lemma 3. By the above analysis, the total number of edges is k (t -1)nk t 2 .

Since t 2 ≥ 1, Lemma 4 implies the following lower bound on tn k (G). Corollary 1. For all k ≥ 1, every graph G with n vertices and m ≥ 1 edges satisfies tn k (G) ≥ m+k kn + 1.

Manipulating Track Layouts

The Wrapping Lemma

Consider a track assignment {V i : 1 ≤ i ≤ t} with a fixed ordering of the tracks. The span of an edge vw

in {V i : 1 ≤ i ≤ t} is |i -j| where v ∈ V i and w ∈ V j . It will also be useful to consider track layouts whose index set is two-dimensional. Let {V i, j : i ≥ 0, 1 ≤ j ≤ b i } be a track assignment of a graph G. Define the partial span of an edge vw ∈ E(G) with v ∈ V i 1 , j 1 and w ∈ V i 2 , j 2 to be |i 1 -i 2 |.
The following lemma describes how to 'wrap' a track layout, and is a generalisation of a result by Dujmović et al. [START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF], which in turn is based on an idea due to Felsner et al. [START_REF] Stefan Felsner | Straight-line drawings on restricted integer grids in two and three dimensions[END_REF].

Lemma 5. 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 ′ α .
Proof. Let {E ℓ : 1 ≤ ℓ ≤ k} be the edge colouring in the given track layout. First we prove (a). By adding extra empty tracks where necessary, we can assume that the track layout is indexed

{V i, j : i ≥ 0, 1 ≤ j ≤ t α , α = i mod (s + 1)} .
For each 0 ≤ α ≤ s and 1 ≤ j ≤ t α , let

W α, j = [ {V i, j : i ≡ α (mod s + 1), i ≥ 0} .
Order W α, j by (V α, j , V α+(s+1), j , V α+2(s+1), j , . . . ) .

Since every edge vw

∈ E(G) has partial span at most s, if v ∈ W α 1 , j 1 and w ∈ W α 2 , j 2 then α 1 = α 2 or j 1 = j 2 . Hence {W α, j : 0 ≤ α ≤ s, 1 ≤ j ≤ t α } is a track assignment of G. For each 1 ≤ ℓ ≤ k, let E ′ ℓ = {vw ∈ E ℓ : v ∈ V i 1 , j 1 ∩W α 1 , j 1 , w ∈ V i 2 , j 2 ∩W α 2 , j 2 , i 1 ≤ i 2 , α 1 ≤ α 2 }
, and

E ′′ ℓ = {vw ∈ E ℓ : v ∈ V i 1 , j 1 ∩W α 1 , j 1 , w ∈ V i 2 , j 2 ∩W α 2 , j 2 , i 1 < i 2 , α 2 < α 1
} . An X-crossing between edges both from some E ′ ℓ (or both from some E ′′ ℓ ) implies that the same edges form an X-crossing in the original track layout. Thus {E ′ ℓ , E ′′ ℓ : 1 ≤ ℓ ≤ k} defines an edge 2k-colouring with no monochromatic X-crossing. Thus we have a (2k, ∑ s α=0 t α )-track layout of G. We now prove (b). Again by adding extra empty tracks where necessary, we can assume that the track layout is indexed

{V i, j : i ≥ 0, 1 ≤ j ≤ t ′ α , α = i mod (2s + 1)}. For each 0 ≤ α ≤ 2s and 1 ≤ j ≤ t ′ α , let W α, j = [ {V i, j : i ≡ α (mod 2s + 1), i ≥ 0} .
Order W α, j by (V α, j , V α+(2s+1), j , V α+2(2s+1), j , . . . ) .

Clearly {W α, j : 0 ≤ α ≤ 2s, 1 ≤ j ≤ t ′ α } is a track assignment of G. It remains to prove that there is no monochromatic X-crossing, where edge colours are inherited from the given track layout. Notice that each

E ℓ = E ′ ℓ ∪ E ′′ ℓ .
As in part (a), edges in E ′ ℓ or in E ′′ ℓ do not form an X-crossing. Consider the track layout defined for part (b). Although the original track layout has maximum partial span s, wrapping modulo 2s + 1 produces edges having partial span greater than s. In particular, edges in E ′ ℓ have partial span at most s, and edges in E ′′ ℓ have partial span at least s + 1. Thus an edge from E ′ ℓ and an edge from E ′′ ℓ do not form an X-crossing. Hence we have a (k,

∑ 2s α=0 t ′ α )-track layout of G.
The full generality of Lemma 5 is used in our companion paper [START_REF] Vida | Layouts of graph subdivisions[END_REF]. For other applications, the following two special cases suffice. By Lemma 5 with b i = b for all i ≥ 0, we have:

Lemma 6. Let {V i, j : i ≥ 0, 1 ≤ j ≤ b} be a (k,t)-

Biconnected Components

Clearly the track-number of a graph is at most the maximum track-number of its connected components. We now prove a similar result for maximal biconnected components (blocks). Lemma 8. For every k ≥ 1, every graph G satisfies:

(a) tn 2k (G) ≤ 2 • max{tn k (B) : B is a block of G}, and (b) tn k (G) ≤ 3 • max{tn k (B) : B is a block of G}.
Proof. Suppose we have a (k,t)-track layout of each block of G, where t = max{tn k (B) : B is a block of G}.

Clearly we can assume that G is connected. Let T be the block-cut-tree of G. That is, there is one vertex in T for each block and for each cut-vertex of G. Two vertices of T are adjacent if one corresponds to a block B and the other corresponds to a cut-vertex v ∈ B. T is a tree, as otherwise a cycle in T would correspond to a single block of G. Root T at a node r corresponding to an arbitrary block.

A node of T that corresponds to a block of G is at even distance from r, and a node of T that corresponds to a cut-vertex of G is at odd distance from r. For all i ≥ 0, let D i be the set of blocks of G whose corresponding node in T is at distance 2i from r. Consider a block B ∈ D i . Let x be the node of T corresponding to B. Let p be the parent node of x in T . Then p corresponds to a cut-vertex of G, which we call the parent cut-vertex of B. Say i ≥ 1. Let y be the parent node of p in T . Then y corresponds to some block B ′ of G. We say B ′ is the parent block of B, and B is a child block of B ′ . Observe that each cut-vertex v is the parent cut-vertex of all but one block containing v. If a vertex v of G is in only one block B then we say v is grouped with B. Otherwise v is a cut-vertex and we say v is grouped with the block for which it is not the parent cut-vertex. Now order each D i firstly with respect to the order of the parent blocks in D i-1 , and secondly with respect to the order of the parent cut-vertices in the track layouts of the parent blocks. More formally, for each i ≥ 1, let < i be a total order of D i such that for all blocks A, B ∈ D i with parent blocks A ′ , B ′ ∈ D i-1 , we have A < i B whenever (1)

A ′ < i-1 B ′ , or (2) A ′ = B ′ , A ∩ A ′ = {v}, B ∩ B ′ =
{w}, and v < w in some track of the (k,t)-track layout of A ′ . (If v and w are in different tracks of the (k,t)-track layout of the parent block then the relative order of A and B is not important.)

For each i ≥ 0 and 1 ≤ j ≤ t, let V i, j be the set of vertices v of G in a some block B ∈ D i such that v is grouped with B, and v is in the j-th track of the track layout of B. Now order each V i, j firstly with respect to the order < i of the blocks in D i , and within a block B, by the order of the j-th track of the track layout of B. Colour each edge e of G by the same colour assigned to e in the (k,t)-track layout of the block containing e. We claim there is no monochromatic X-crossing.

The parent cut-vertex of a block B is grouped with the parent block of B, and no block and its parent block are in the same D i . Thus if vw is an edge with v ∈ V i, j 1 and w ∈ V i, j 2 then both v and w are grouped with the block containing vw. Since within each track vertices are ordered primarily by their block, and by assumption there is no monochromatic X-crossing between edges in the same block, there is no monochromatic X-crossing between tracks V i, j 1 and V i, j 2 for all i ≥ 0 and 1 ≤ j 1 , j 2 ≤ t.

If vw is an edge with v ∈ V i 1 , j 1 and w ∈ V i 2 , j 2 for distinct i 1 and i 2 , then without loss of generality, i 2 = i 1 + 1 and v is the parent cut-vertex of the block containing vw. Since sibling blocks are ordered with respect to the ordering of their parent cut-vertices, there is no X-crossing amongst edges between tracks V i 1 , j 1 and V i 2 , j 2 for all i 1 , i 2 ≥ 0 and 1 ≤ j 1 , j 2 ≤ t. Thus {V i, j : i ≥ 0, 1 ≤ j ≤ t} is a k-edge colour track layout of G such that every edge has a partial span of one. By Lemma 6, G has tn 2k (G) ≤ 2t, and G has tn k (G) ≤ 3t.

Tracks vs. Colours

We now show how to reduce the number of tracks in a track layout, at the expense of increasing the number of edge colours. Lemma 9. Let G be a (k,t)-track graph with maximum span s (≤ t -1). For every vertex colouring

{V i : 1 ≤ i ≤ c} of G, there is a (2sk, c)-track layout of G with tracks {V i : 1 ≤ i ≤ c}.
Proof. Let {T j : 1 ≤ j ≤ t} be a (k,t)-track layout of G with maximum span s and edge colouring {E ℓ :

1 ≤ ℓ ≤ k}. Given a vertex colouring {V i : 1 ≤ i ≤ c} of G, order each V i by (V i ∩ T 1 ,V i ∩ T 2 , . . . ,V i ∩ T t ). Thus {V i : 1 ≤ i ≤ c} is a c-track
assignment of G. Now we define an edge 2sk-colouring. For all integers ℓ and α such that 1 ≤ ℓ ≤ k and 1 ≤ |α| ≤ s, let

E ℓ,α = {vw ∈ E ℓ : v ∈ V i 1 ∩ T j 1 , w ∈ V i 2 ∩ T j 2 , i 1 < i 2 , j 1 -j 2 = α} .
Consider two edges vw and xy in some E ℓ,α between a pair of tracks V i 1 and

V i 2 . Without loss of generality i 1 < i 2 , v ∈ V i 1 ∩ T j 1 , w ∈ V i 2 ∩ T j 1 +α , x ∈ V i 1 ∩ T j 2 , y ∈ V i 2 ∩ T j 2 +α
, and j 1 ≤ j 2 . If j 1 = j 2 then vw and xy are between the same pair of tracks in the given track layout, and the relative order of the vertices is preserved. Thus if vw and xy form an X-crossing in the c-track assignment then they are coloured differently. If j 1 < j 2 then v < i 1 x and w < i 2 y, and the edges do not form an X-crossing. Hence vw and xy do not form a monochromatic X-crossing, and we have a (2sk, c)-track layout of G.

We now show how to reduce the number of edge colours in a track layout, at the expense of increasing the number of tracks. A vertex colouring is acyclic if there is no bichromatic cycle; that is, every cycle receives at least three colours. The acyclic chromatic number of a graph G, denoted by χ a (G), is the minimum number of colours in an acyclic vertex colouring of G. This concept was introduced by Grünbaum [START_REF] Branko Gr Ünbaum | Acyclic colorings of planar graphs[END_REF], and has since been widely studied [START_REF] Noga Alon | Acyclic coloring of graphs[END_REF][START_REF] Noga Alon | On acyclic colorings of graphs on surfaces[END_REF][START_REF] Berman | Critical graphs for acyclic colorings[END_REF][START_REF] Borodin | On acyclic colorings of planar graphs[END_REF][START_REF] Borodin | Acyclic list 7-coloring of planar graphs[END_REF][START_REF] Borodin | On the maximum average degree and the oriented chromatic number of a graph[END_REF][START_REF] Borodin | Acyclic colouring of 1-planar graphs[END_REF][START_REF] Borodin | Acyclic colourings of planar graphs with large girth[END_REF][START_REF] Borodin | Acyclic colourings of planar graphs with large girth[END_REF][START_REF] Šteȋn | Every 4-valent graph has an acyclic 5-coloring[END_REF][START_REF] Fertin | Minimum feedback vertex set and acyclic coloring[END_REF][START_REF] Fertin | On star coloring of graphs[END_REF][START_REF] Alexandr | Note to the paper of Grünbaum on acyclic colorings[END_REF][START_REF] Ne | Colorings and homomorphisms of minor closed classes[END_REF]. By Lemma 1, each 2-track subgraph in an (edge-monochromatic) track layout is a forest of caterpillars. Thus the underlying vertex colouring is acyclic. Hence,

χ a (G) ≤ tn(G) . (1)
A number of the results in this paper bound the acyclic chromatic number by various 'geometric' graph parameters. Many other variations of the chromatic number (including star chromatic number [START_REF] Albertson | Coloring with no 2-colored P 4 's[END_REF][START_REF] Fertin | On star coloring of graphs[END_REF][START_REF] Branko Gr Ünbaum | Acyclic colorings of planar graphs[END_REF] and oriented chromatic number [START_REF] Kostochka | Acyclic and oriented chromatic numbers of graphs[END_REF][START_REF] Sopena | Good and semi-strong colorings of oriented planar graphs[END_REF][START_REF] Sopena | Oriented graph coloring[END_REF]) are bounded by the acyclic chromatic number. Thus our results also apply to these other types of colourings-we omit the details.

Alon and Marshall [START_REF] Marshall | Homomorphisms of edge-colored graphs and Coxeter groups[END_REF] proved the following application of acyclic colourings that we will repeatedly use. Loosely speaking, it says how to transform an edge colouring into a vertex colouring. A vertex colouring C 1 is a refinement of a vertex colouring C 2 if every colour class of C 1 is a subset of some colour class of C 2 .

Lemma 10. [2] Given an edge k-colouring of a graph G, any acyclic c-colouring of G can be refined to a ck c-1 -colouring so that the edges between any pair of (vertex) colour classes are monochromatic.

The following result, which is implicit in Lemma 5.3 of Dujmović et al. [START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF], easily follows from Lemma 10.

Theorem 2. [26]

Let G be a (k,t)-track graph in which the underlying vertex t-colouring is acyclic. Then G has track-number tn(G) ≤ tk t-1 .

The following result is similar to Theorem 2 but without the assumption that G has an acyclic colouring. A track layout T 1 is a refinement of a track layout T 2 if every track in T 1 is a subset of, and has the same order as, some track in T 2 . Theorem 3. Every (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. That is, G has track-number tn(G) ≤ t • 4 ( k 2 )(t-1) .
We will prove Theorem 3 by a series of lemmas. Recall that a crossing triple in a track assignment is a set of three edges, each pair of which forms an X-crossing. The following result is the key idea.

Lemma 11. Every 2-track assignment with no crossing triple can be refined to an (edge-monochromatic) 8-track layout, with four tracks arising from each of the two given tracks.

Proof. Let {A, B} be a 2-track assignment of a graph G with no crossing triple. We consider each track to be ordered left-to-right. Construct a path P starting at the first vertex in A as follows. If v is the current endpoint of P, choose vw to be the next edge in P, where w is the rightmost vertex in the track that does not contain v, such that G ∪ vw has no crossing triple. (Note that vw is not necessarily an edge of G.) Repeat this process until v is the rightmost vertex in B. Then {A, B} is a 2-track assignment of G ∪ P with no crossing triple.

In the construction of P, we can always choose the edge vw, since if uv is the edge most recently added to P, then the first vertex w to the right of u satisfies the conditions on w (since if {vw, e 1 , e 2 } is a crossing triple, then {uv, e 1 , e 2 } is a crossing triple, or v was not chosen rightmost.) This also proves that P is plane (that is, non-self-crossing). Moreover, P is an induced path, as otherwise some vertex in P would not be rightmost.

Claim. Each edge of G crosses at most one edge of P.

Proof. Assume for the sake of contradiction that an edge xy of G crosses two edges of P. Then xy crosses some 2-edge path uvw ∈ P, such that without loss of generality u ∈ B, v ∈ A, w ∈ B, and u < w in B. We can assume that x is the rightmost vertex in its track that has an incident edge xy that crosses uvw, and x < v in A or x < u in B.

Case 1. x ∈ A (see Figure 3(a)): Since vw was added to P (and vy was not added to P), there are two edges pq, rs ∈ E(G) (with p, r ∈ A and q, s ∈ B), such that {pq, rs, vy} is a crossing triple. If pq or rs does not cross xy, then x < p < v or x < r < v, in which case pq or rs crosses uvw with p > x or r > x, which contradicts our choice of x. Otherwise {pq, rs, xy} is a crossing triple, which is again a contradiction.

Case 2. x ∈ B (see Figure 3(b)): Since uv was added to P (and uy was not added to P), there are two edges pq, rs ∈ E(G) (with p, r ∈ A and q, s ∈ B), such that {pq, rs, uy} is a crossing triple. If pq or rs does not cross xy then x < q < u or x < s < u, in which case pq or rs crosses uvw with x < q or x < s, which contradicts our choice of x. Otherwise {pq, rs, xy} is a crossing triple, which is again a contradiction. andw t is the last vertex in B, and

Let P = (v 1 , w 1 , v 2 , w 2 , . . . , v t , w t ), where v 1 is the first vertex in A, and v 1 < v 2 < • • • < v t in A,
w 1 < w 2 < • • • < w t in B.
For 1 ≤ i ≤ t -1, let A i be the subset of A consisting of the vertices strictly between v i and v i+1 . Let A t be the subset of A consisting of the vertices strictly after v t . Let B 0 be the subset of B consisting of the vertices strictly before w 1 . For 1 ≤ i ≤ t -1, let B i be the subset of B consisting of the vertices strictly between w i and w i+1 .

Let X 1 = {v i : i odd}, X 2 = {v i : i even}, X 3 = ∪{A i : i odd}, and X 4 = ∪{A i : i even}. Let Y 1 = {w i : i odd}, Y 2 = {w i : i even}, Y 3 = ∪{B i : i odd}, and Y 4 = ∪{B i : i even}. Consider each of X 1 , X 2 , X 3 and X 4 to be tracks ordered as in A. Consider each of Y 1 , Y 2 , Y 3 and Y 4 to be tracks ordered as in B. Note that every vertex of G is in one of these tracks. We claim that there is no X-crossing between these tracks.

u w y s q x v p r A B (a) u w x s q y v p r A B (b)
Since P is an induced path of G ∪ P, every edge of G[X 1 ∪ X 2 ,Y 1 ∪Y 2 ] is in P. Since P is non-crossing, there is no X-crossing between tracks X α and Y β for all α, β ∈ {1, 2}.

Consider the subgraphs

G[X 1 ,Y 3 ∪Y 4 ] and G[X 2 ,Y 3 ∪Y 4 ]. By the construction of P, G[X 1 ,Y 3 ∪Y 4 ] only has edges v i x where i is odd and x ∈ B i-1 ∪ B i-2 , and G[X 2 ,Y 3 ∪Y 4 ] only has edges v i x where i is even and x ∈ B i-1 ∪ B i-2 . Thus G[X 1 ,Y 3 ∪ Y 4 ] and G[X 2 ,Y 3 ∪ Y 4 ] consist of non-crossing stars rooted at vertices v i of P. Similarly, G[Y 1 , X 3 ∪ X 4 ] and G[Y 2 , X 3 ∪ X 4 ] consist of non-crossing stars rooted at vertices w i ∈ P. Thus there is no X-crossing in G[X 1 ,Y 3 ∪Y 4 ], G[X 2 ,Y 3 ∪Y 4 ], G[Y 1 , X 3 ∪ X 4 ] and G[Y 2 , X 3 ∪ X 4 ].
Now, assume for the sake of contradiction that two edges vw and xy in G[X 3 ,Y 3 ] form an X-crossing. Say v < x in A and y < w in B. Since no edge of G[X 3 ,Y 3 ] crosses two edges of P, we have v, x ∈ A i and w, y ∈ B i for some i. Thus v < x < v i+1 and w i < y < w. Hence {vw, xy, w i v i+1 } is a crossing triple, which is a contradiction. It is simple to verify that the same arguments prove that there is no X-crossing in

G[X 3 ,Y 4 ], G[X 4 ,Y 3 ] and G[X 4 ,Y 4 ].
This completes the proof that

{X 1 , X 2 , X 3 , X 4 ,Y 1 ,Y 2 ,Y 3 ,Y 4 } is the desired 8-track layout of G. A : B : A 1 ⊆ X 3 A 3 ⊆ X 3 A 5 ⊆ X 3 A 2 ⊆ X 4 A 4 ⊆ X 4 A 6 ⊆ X 4 B 1 ⊆ Y 3 B 3 ⊆ Y 3 B 5 ⊆ Y 3 B 0 ⊆ Y 4 B 2 ⊆ Y 4 B 4 ⊆ Y 4 v 1 ∈ X 1 v 3 ∈ X 1 v 5 ∈ X 1 v 2 ∈ X 2 v 4 ∈ X 2 v 6 ∈ X 2 w 1 ∈ Y 1 w 3 ∈ Y 1 w 5 ∈ Y 1 w 2 ∈ Y 2 w 4 ∈ Y 2 w 6 ∈ Y 2
: 1 ≤ α ≤ 4} of G[E i ∪ E j ], where every X i, j α ⊆ A and Y i, j α ⊆ B. For each vertex v ∈ A, define the vector (X i, j α : {i, j} ∈ [k] 2 , v ∈ X i, j α ). For each vertex w ∈ B, define the vector (Y i, j α : {i, j} ∈ [k] 2 , w ∈ Y i, j α )
. Now group the vertices with a common vector into a track, ordered by A or B accordingly. Since each of the 8-track layouts is a refinement of {A, B}, the order of the vertices within each of the 8-track layouts is preserved. If two edges coloured i form an X-crossing, then the same pair of edges would form an X-crossing in the (k, 2)-track layout of G. If two edges coloured i and j form an X-crossing, then the same edges would form an X-crossing in the 8-track layout of G[E i ∪ E j ]. Hence there is no X-crossing. The number tracks for each of A and B is 4

( k 2 ) .
Proof of Theorem 3. Let {V 1 ,V 2 , . . . ,V t } be the tracks in a (k,t)-track layout of G. For each vertex v ∈ V i , and for every other track V j , let φ j (v) be the track containing v in the track layout of G[V i ,V j ] determined by Lemma 12, where 1 ≤ φ j (v) ≤ 4 ( k 2 ) . For each vertex v ∈ V i , define the vector

(i; φ 1 (v), . . . , φ i-1 (v), φ i+1 (v), . . . , φ t (v)) .
Group the vertices with a common vector into a track, ordered by the appropriate

V i . Since each track layout of G[V i ,V j
] is a refinement of {V i ,V j }, the order of the vertices within each track layout of G[V i ,V j ] is preserved. If two edges are between the same pair of tracks, then their endpoints must be from the same pair of colour classes. Thus there is no X-crossing, as otherwise there would be an X-crossing in the track layout of some G[V i ,V j ]. The total number of tracks is t • 4 ( k 2 )(t-1) .

Note that Lemma 12 can re-stated as follows:

Corollary 2. The vertices of a (k, 2)-track graph can be coloured with 2 • 4 ( k 2 ) colours so that each bichromatic subgraph is a plane caterpillar; that is, each bichromatic subgraph has no X-crossing.

Theorem 3 and (1) imply:

Corollary 3. Acyclic chromatic number is bounded by track-number. In particular, every (k,t)-track graph G has acyclic chromatic number χ a (G) ≤ t • 4 ( k 2 )(t-1) . Note that the converse of Corollary 3 is not true. Let K ′′ n be the graph obtained from the complete graph K n by subdividing every edge twice. Colour each original vertex of K n red, and colour the two division vertices of each edge blue and green. Clearly there is no bichromatic cycle. Thus χ a (K ′′ n ) = 3 for n ≥ 3. However, K ′′ n has track-number tn(K ′′ n ) ∈ Ω(n 1/4 ) [START_REF] Vida | Layouts of graph subdivisions[END_REF]. Thus track-number is not bounded by acyclic chromatic number.

Stack and Queue Layouts

Let σ be 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 without loss of generality L(e) e) then e and f nest, and f is nested inside e.

< σ L( f ). If L(e) < σ L( f ) < σ R(e) < σ R( f ) then e and f cross. If L(e) < σ L( f ) < σ R( f ) < σ R(
A stack (respectively, queue) in σ is a set of edges no two of which cross (nest) in σ. 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 σ. A graph admitting a k-stack (queue) layout is called a k-stack (queue) graph. The stack-number (queue-number) of a graph G, denoted by sn(G) (qn(G)), is the minimum k such that G is a k-stack (k-queue) graph. Note that stack-number is also called page-number and book-thickness in the literature.

Bernhart and Kainen [START_REF] Bernhart | The book thickness of a graph[END_REF] observed that the 1-stack graphs are precisely the outerplanar graphs, and that 2-stack graphs are characterised as the subgraphs of planar Hamiltonian graphs. Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF] characterised 1-queue graphs as the 'arched levelled planar' graphs. See our companion paper [START_REF] Vida | On linear layouts of graphs[END_REF] for other results and numerous references related to stack and queue layouts.

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 5 Lemma 13 implies that a (k, 2)-track layout can be thought of as a k-stack layout of a bipartite graph in which the two colour classes are 'separated' in the ordering. In Corollary 2 we proved that the vertices of (k, 2)-track layout can be coloured with 2 • 4 ( k 2 ) colours so that each bichromatic subgraph is crossing-free. This result can be generalised as follows.

Theorem 4. Every k-stack graph has a vertex 80 ( k

2 ) -colouring so that each bichromatic subgraph is contained in a single stack, and is thus crossing-free and outerplanar.

Proof. Every 2-stack graph is planar [START_REF] Bernhart | The book thickness of a graph[END_REF], and thus has an acyclic 5-colouring [START_REF] Borodin | On acyclic colorings of planar graphs[END_REF]. By Lemma 10 using the stack assignment as an edge 2-colouring, every 2-stack graph has a vertex colouring with 5 • 2 4 = 80 colours, so that the edges of each bichromatic subgraph are in a single stack. Now suppose that G is a k-stack graph. Let {E 1 , E 2 , . . . , E k } be the stacks. For each pair {i, j}

∈ [k]
2 , there is a vertex 80-colouring of G[E i ∪E j ], such that the edges in each bichromatic subgraph are contained in a single stack. Let φ i, j (v) ∈ {1, 2, . . . , 80} be the colour assigned to each vertex v. Now colour v by the vector φ(v) = (φ i, j (v) : {i, j} ∈ [k] 2 ). Suppose there are two edges vw and xy in some bichromatic subgraph of φ, and vw and xy are in distinct stacks E i and E j . Without loss of generality, φ(v) = φ(x) and φ(w) = φ(y). Thus φ i, j (v) = φ i, j (x) and φ i, j (w) = φ i, j (y). Hence in the vertex 80-colouring of G[E i ∪ E j ], there is a bichromatic subgraph with two edges in distinct stacks, which is a contradiction. Thus each bichromatic subgraph of φ is contained in a single stack. The number of colours is 80 ( k 2 ) .

Theorem 5. Acyclic chromatic number is bounded by stack-number. In particular, every k-stack graph G has acyclic chromatic number χ a (G) ≤ 80 k(2k-1) .

Proof. The edges of an outerplanar graph can be partitioned into two acyclic subgraphs [START_REF] St | Decomposition of finite graphs into forests[END_REF]. Thus G has a 2k-stack layout in which each stack is acyclic. The result follows from Theorem 4.

Note that the converse of Theorem 5 is not true. Blankenship and Oporowski [START_REF] Blankenship | Book Embeddings of Graphs[END_REF][START_REF] Oporowski | Drawing subdivisions of complete and complete bipartite graphs on books[END_REF][START_REF] Oporowski | Book embeddings of graphs and minor-closed classes[END_REF] proved that the stack-number of K ′′ n is unbounded, but χ a (K ′′ n ) = 3 for n ≥ 3 (see Section 4). Thus stack-number is not bounded by acyclic chromatic number.

Queue and Track Layouts

Consider how to convert a track layout into a queue layout. The following lemma was proved by Dujmović et al. [START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF] for k = 1, and with t = 2 is nothing more than Lemma 13(b). Lemma 14. 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.

Proof. Let {V i : 1 ≤ i ≤ t} be a (k,t)-track layout of a graph G with maximum span s and edge colouring {E ℓ : 1 ≤ ℓ ≤ k}. Let σ be the vertex ordering (V 1 ,V 2 , . . . ,V t ) of G. Let E ℓ,α be the set of edges in E ℓ with span α in the given track layout. Two edges from the same pair of tracks are nested in σ if and only if they form an X-crossing in the track layout. Since no two edges in E ℓ form an X-crossing in the track layout, no two edges in E ℓ and between the same pair of tracks are nested in σ. If two edges not from the same pair of tracks have the same span then they are not nested in σ. (This idea is due to Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF].) Thus no two edges are nested in each E ℓ,α , and we have a ks-queue layout of G.

While the relationship between stack and track layouts is not as pronounced as that between queue and track layouts, Lemmata 9 and 13 imply the following analogous result to Lemma 14 for stack layouts of bipartite graphs.

Lemma 15.

Stack-number is bounded by track-number for bipartite graphs. In particular, every bipartite (k,t)-track graph with maximum span s (≤ t -1) has a 2ks-stack layout. Now consider how to convert a vertex ordering into a track layout. The proof of the next result follows immediately from the definitions, and is illustrated in Figure 6.

Proof. Let σ be the vertex ordering in a q-queue layout of G with queues {E ℓ : 1 ≤ ℓ ≤ q}. Let {(V i , σ) : 1 ≤ i ≤ c} be a c-track assignment of G, and for each 1 ≤ ℓ ≤ q, let

E ′ ℓ = {vw ∈ E ℓ : v ∈ V i , w ∈ V j , i < j, v < σ w}, and E ′′ ℓ = {vw ∈ E ℓ : v ∈ V i , w ∈ V j , i < j, w < σ v} .
By Lemma 16, an X-crossing in the track assignment between edges both from some E ′ ℓ (or both from some E ′′ ℓ ) implies that these edges are nested in σ. Since no two edges in E ℓ are nested in σ, the set {E ′ ℓ , E ′′ ℓ : 1 ≤ ℓ ≤ q} defines an edge 2q-colouring with no monochromatic X-crossing in the track assignment. Thus we have a (2q, c)-track layout of G.

Lemma 18 is similar to a result by Pemmaraju [START_REF] Pemmaraju | Exploring the Powers of Stacks and Queues via Graph Layouts[END_REF] which says that a queue layout can be 'separated' by a vertex colouring, although the proof by Pemmaraju, which is based on the characterisation of 1-queue graphs as 'arched levelled planar', is much longer. Pemmaraju [START_REF] Pemmaraju | Exploring the Powers of Stacks and Queues via Graph Layouts[END_REF] used separated queue layouts to prove the next result, which follows from Lemmata 13 and 18.

Theorem 6. [48]

Stack-number is bounded by queue-number for bipartite graphs. In particular, sn(G) ≤ 2 qn(G) for every bipartite graph G.

The 2-track thickness of a bipartite graph G is the minimum k such that G has a (k, 2)-track layout (see [START_REF] Vida | Layouts of graph subdivisions[END_REF]). Lemmata 13 and 18 imply: Theorem 7. Queue-number and 2-track thickness are tied for bipartite graphs. In particular, for every bipartite graph G, if qn(G) ≤ k then G has a (2k, 2)-track layout, and if G has a (k, 2)-track layout then qn(G) ≤ k.

In our companion paper [START_REF] Vida | On linear layouts of graphs[END_REF], we prove that every q-queue graph is 4q-colourable. Thus Lemma 18 implies: Corollary 4. Every q-queue graph has a (2q, 4q)-track layout.

The next corollary of Theorem 2 and Lemma 18 is by Dujmović et al. [START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF].

Corollary 5. [26]

Every q-queue graph G with acyclic chromatic number χ a (G) ≤ c has track-number tn(G) ≤ c(2q) c-1 .

Nešetřil and Ossona de Mendez [START_REF] Ne | Colorings and homomorphisms of minor closed classes[END_REF] proved that every proper minor-closed graph family has bounded acyclic chromatic number. Thus Corollary 5 implies that for every proper minor-closed graph family, track-number is bounded by queue-number [START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF]. However, this does not imply that track-number is bounded by queue-number for all graphs. For example, in our companion paper [START_REF] Vida | Layouts of graph subdivisions[END_REF] we prove that there are 2-queue graphs with unbounded clique minors, for which we cannot apply the result of Nešetřil and Ossona de Mendez [START_REF] Ne | Colorings and homomorphisms of minor closed classes[END_REF]. By Theorem 3 and Corollary 4, we have the following result which is qualitatively stronger than Corollary 5. Theorem 8. Track-number is bounded by queue-number. In particular, every graph G with queue-number qn(G) ≤ q has track-number tn(G) ≤ 4q • 4 q(2q-1)(4q-1) . Theorem 8 and (1) imply: Corollary 6. Acyclic chromatic number is bounded by queue-number. In particular, every graph G with queue-number qn(G) ≤ q has acyclic chromatic number χ a (G) ≤ 4q • 4 q(2q-1)(4q -1) .

Again the converse of Corollary 6 is not true. In particular, qn(K ′′ n ) ∈ Ω(n 1/4 ) [START_REF] Vida | Layouts of graph subdivisions[END_REF], but χ a (K ′′ n ) = 3 for n ≥ 3 (see Section 4). Thus queue-number is not bounded by acyclic chromatic number.

Lemma 10 and Corollary 6 imply:

Theorem 9. Every q-queue graph has a (4q • 4 q(2q-1)(4q-1) )q 4q•4 q(2q-1)(4q-1) -1 -colouring in which each bichromatic subgraph is contained in a single queue, and is thus (arched-levelled) planar.

Theorem 8 and Lemma 14 prove the following result, which is one of the main contributions of the paper.

Theorem 10. Queue-number and track-number are tied.

1-Queue Graphs

In the case of 1-queue graphs, much improved bounds can be obtained. Di Giacomo and Meijer [START_REF] Di | Track drawings of graphs with constant queue number[END_REF] proved that every 1-queue graph has a 5-track layout, and that there exists a 1-queue graph with tracknumber at least 4. We now prove that the lower bound is the right answer.

Theorem 11. Every 1-queue graph has a (2, 3)-track layout and a 4-track layout.

To prove Theorem 11 we will use the following characterisation of 1-queue graphs that may be of independent interest. It is similar but not the same as the characterisation in terms of 'arched levelled' planar graphs due to Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF].

Lemma 19.

A graph G has a 1-queue layout if and only if G has a track layout {V i : 1 ≤ i ≤ t} with maximum span two, such that for every edge vw ∈ E(G) that has span two (v ∈ V i , w ∈ V i+2 ), w is the first vertex in V i+2 , and there is no edge xy ∈ E(G) with v < i x ∈ V i and y ∈ V i+1 .

Proof. Suppose that T = {V i : 1 ≤ i ≤ t} is a track layout of a graph G that satisfies the conditions of the lemma. Let σ be the vertex ordering (V 1 ,V 2 , . . . ,V t ). Suppose that there is an edge xy nested inside another edge vw in σ. Without loss of generality, v < σ x < σ y < σ w. By the proof of Lemma 14, edges that have the same span in T are not nested in σ. Thus the span of xy is one, and the span of vw is two. Hence v ∈ V i and w ∈ V i+2 for some 1 ≤ i ≤ t -2. By assumption, w is the first vertex in its track. Thus x ∈ V i and y ∈ V i+1 . But this contradicts the assumption about T . Thus no two edges are nested in σ, and we have a 1-queue layout of G. Now suppose that σ is the vertex ordering in a 1-queue layout of a graph G. Partition the vertices into non-empty independent sets V 1 ,V 2 , . . . ,V t such that σ = (V 1 ,V 2 , . . . ,V t ), and for all 2 ≤ i ≤ t, there exists an edge from the first vertex in V i to some vertex in V i-1 . Such a partition can be computed greedily as follows. First let V 1 be the largest independent set at the start of σ. Then for all i = 2, 3, . . . ,t, let V i be the largest independent set starting with the vertex immediately after the last vertex in V i-1 . We claim that T = {(V i , σ) : 1 ≤ i ≤ t} is the desired track layout.

Since σ has no nested edges, by Lemma 16, T is a track layout (with no X-crossing). For all s ≥ 3, there is no edge in any G[V i ,V i+s ], as otherwise it would be nested in σ with the edge from the first vertex in V i+2 to some vertex in V i+1 . Thus the track layout has span at most two. If an edge vw has span two with v ∈ V i and w ∈ V i+2 , then w is the first vertex in V i+2 , as otherwise vw would be nested with the edge between the first vertex in V i+2 and some vertex in V i+1 . Moreover, there is no edge xy ∈ E(G) with v < i x ∈ V i and y ∈ V i+1 , as otherwise xy would be nested inside vw in σ.

Proof of Theorem 11. Let T 1 = {V i : i ≥ 0} be the track layout of G from Lemma 19. Since T 1 has maximum span at most two, G has a (2, 3)-track layout and a 5-track layout by Lemma 7. Let T 2 = {W 0 ,W 1 ,W 2 ,W 3 } be the track assignment obtained by wrapping T 1 modulo four; that is, for j ∈ {0, 1, 2, 3},

W j = (V j ,V j+4 ,V j+8 , . . .) .
An edge that has span one in T 1 has span one or three in T 2 . An edge that has span two in T 1 has span two in T 2 . Suppose for the sake of contradiction that two edges vw and xy form an X-crossing in T 2 . As in Lemma 5, two edges that have span one in T 1 , do not form an X-crossing in T 2 . Two edges, one with span one and the other with span two in T 1 do not form an X-crossing in T 2 , as they have different spans in T 2 . Thus vw and xy both have span two in T 1 . Thus, by the above observation and without loss of generality, v is the first vertex in some V i and x is the first vertex in some V j with i < j. Moreover, j ≥ i + 2 since v, w, x and y belong to two tracks of T 2 . Thus either y ∈ V ℓ such that ℓ > i or y ∈ V i and y > v. In either case, as in Lemma 5, vw and xy do not form an X-crossing in T 2 , which is a contradiction, as desired.

Geometric Thickness

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, and monochromatic edges do not cross [START_REF] Dillencourt | Geometric thickness of complete graphs[END_REF][START_REF] Duncan | The geometric thickness of low degree graphs[END_REF][START_REF] Kainen | Thickness and coarseness of graphs[END_REF]. Stack-number (when viewed as 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 θ(G) ≤ sn(G) for every graph G. While it is an open problem whether stack number is bounded by track-number or by queuenumber (see our companion paper [START_REF] Vida | Layouts of graph subdivisions[END_REF]), we prove the weaker results that geometric thickness is bounded by track-number, and geometric thickness is bounded by queue-number. Theorem 12. Geometric thickness is bounded by track-number. In particular, every (k,t)-track graph G has geometric thickness θ(G) ≤ k⌈ t 2 ⌉⌊ t 2 ⌋.

Proof. Let p ≥ t be a prime. Position the j-th vertex in the i-th track at (i, p j + (i 2 mod p)). Wood [START_REF] Wood | Grid drawings of k-colourable graphs[END_REF] proved that in this layout no three vertices are collinear, unless all three are in a single track. Since a track is an independent set, the only vertices that an edge intersects are its own endpoints. The vertices in each track are positioned on a line parallel to the Y -axis, in the order defined by the track layout. Thus monochromatic edges between any pair of tracks do not cross. If we let each pair of tracks use a distinct palette of k edge colours, then we obtain a drawing of G with k t 2 edge colours, such that monochromatic edges do not cross. That is, θ(G) ≤ k t 2 . This bound can be improved by partitioning the pairs of tracks into sets that can use the same palette of k colours. This amounts to edge-colouring the complete graph K t with a fixed vertex ordering (v 1 , v 2 , . . . , v t ), so that overlapping edges receive distinct colours. To this end, define a partial order on E(K t ) as follows. For all edges v i v j and v a v b (with i < j and a

< b), let v i v j ≺ v a v b if j ≤ a.
Clearly is a partial order on E(K t ), such that distinct edges are overlapping if and only if they are incomparable under . By Dilworth's Theorem [START_REF] Dilworth | A decomposition theorem for partially ordered sets[END_REF], there is a partition of E(K t ) into r sets, each pairwise non-overlapping, where r is the size of the largest set of pairwise overlapping edges. Clearly r = ⌈ t 2 ⌉⌊ t 2 ⌋. For each such set, assign a distinct palette of k colours to the edges between pairs of tracks corresponding to edges of K t in this set. In total we have kr edge colours, and θ(G) ≤ kr = k⌈ t 2 ⌉⌊ t 2 ⌋. Theorem 12 and Lemma 18 imply: Note that queue-number is not bounded by geometric thickness. For example, the graph K ′ n obtained from K n by subdividing every edge once has geometric thickness two [START_REF] David Eppstein | Separating geometric thickness from book thickness[END_REF] but has queue-number Θ( √ n) [START_REF] Vida | Layouts of graph subdivisions[END_REF]. Similarly, acyclic chromatic number is not bounded by geometric thickness, since χ a (K ′ n ) ∈ Θ( √ n) [START_REF] Wood | Acyclic, star and oriented colourings of graph subdivisions[END_REF]. In fact, in Lemma 20 below we prove a stronger result that provides a counterpoint to Theorems 4 and 9.

Let G be a graph with a straight line drawing in the plane with the vertices in convex position. Suppose that there is a k-colouring of the edges so that monochromatic edges do not cross. Then Theorem 4 implies G has a vertex colouring with 80 ( k 2 ) colours so that each bichromatic subgraph is plane (that is, no two edges cross). Theorem 9 gives a similar result for k-queue graphs. This type of result does not extend to the case of graphs with geometric thickness k ≥ 2. Again our example is K ′ n which has geometric thickness two [START_REF] David Eppstein | Separating geometric thickness from book thickness[END_REF].

Lemma 20. For every c ∈ N there is an n ∈ N, such that in every vertex c-colouring of K ′ n there is a bichromatic subgraph that is not planar.

To prove Lemma 20 we need the following lemma. Proof. For each vertex v ∈ V i and for all j = i, let φ j (v) be the colour assigned to v in an acyclic kcolouring of G[V i ,V j ]. Colour v by the vector φ(v) = (i; φ 1 (v), . . . , φ i-1 (v), φ i+1 (v), . . . , φ c (v)). If C is a bichromatic cycle between colour classes (i; λ 1 , . . . , λ i-1 , λ i+1 , . . . , λ c ) and ( j; γ 1 , . . . , γ j-1 , γ j+1 , . . . , γ c ), then C is a bichromatic cycle between colour classes λ j and γ i in the acyclic colouring of G[V i ,V j ]. Thus φ is an acyclic colouring of G. The number of colours is c • k c-1 .

Proof of Lemma 20. Suppose on the contrary that there is a c ∈ N such that every K ′ n has a vertex ccolouring in which every bichromatic subgraph is planar. By Lemma 21 and since planar graphs have acyclic 5-colourings [START_REF] Borodin | On acyclic colorings of planar graphs[END_REF], every K ′ n has a c • 5 c-1 -acyclic colouring. However, the acyclic chromatic number of K ′ n is Ω( √ n) [START_REF] Wood | Acyclic, star and oriented colourings of graph subdivisions[END_REF]. Thus we obtain a contradiction for sufficiently large n. Lemma 24. For every outerplanar graph H, there is a planar graph G with track-number tn(G) ≥ tn(H) + 3.

Proof. We construct G incrementally. Start with an edge v 1 v 2 . Let t = tn(H) and n = 2t + 1. Add n new vertices {w 1 , w 2 , . . . , w n } each adjacent to both v 1 and v 2 . Let H 1 , H 2 , . . . , H n be copies of H. For all 1 ≤ j ≤ n, add an edge between w j and every vertex of H j . As illustrated in Figure 8, G is planar. Suppose that G has a (t + 2)-track layout. Without loss of generality, v i is in track i. Thus {w 1 , w 2 , . . . , w n } are in tracks {3, 4, . . . ,t + 2}. Hence there are three w j vertices in a single track. Without loss of generality, w 1 < w 2 < w 3 in track 3. No vertex x of H 2 is in track 1 or 2, as otherwise xw 2 would form an X-crossing with one of {v 1 w 1 , v 1 w 3 , v 2 w 1 , v 2 w 3 }. No vertex x of H 2 is in track 3, since x and w 2 are adjacent, and w 2 is in track 3. Thus all the vertices of H 2 are in tracks {4, 5, . . . ,t + 2}, implying tn(H) ≤ t -1, which is a contradiction. Therefore tn(G) ≥ t + 3. Proof. Let G be the planar graph from Theorem 13. Let G ′ be the graph obtained from G by the following construction. For each edge vw of G, add six new vertices to G ′ , each adjacent to v and w. Clearly G ′ is planar. Dujmović et al. [START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF] proved that if G ′ has an improper 6-track layout, then G has a (proper) 6-track layout. Thus G ′ has no improper 6-track layout by Theorem 13.

v 1 v 2 w 1 H 1 w 2 H 2 ✁ ✂ w n H n

Computational Complexity

We conclude with some open problems regarding the computational complexity of determining whether a given graph admits a particular type of track layout. Note that there is a simple linear time algorithm to recognise 2-track graphs. Is it N P -complete to recognise (2, 2)-track graphs? Is it N P -complete to recognise 3-track graphs? Given a vertex ordering σ of a graph G, is it N P -complete to test if G has a 3-colouring {V 1 ,V 2 ,V 3 } such that {(V 1 , σ), (V 2 , σ), (V 3 , σ)} is a track layout?

Fig. 1 :

 1 Fig. 1: A 2-track layout of a forest of caterpillars.

Theorem 1 . [ 26 , 28 ]

 12628 Let G be a c-colourable t-track graph with n vertices. Then(a) G has a O(t) × O(t) × O(n) straight-line drawing with O(t 2 n) volume, and (b) G has a O(c) × O(c 2 t) × O(c 4 n) straight-line drawing with O(c 7 tn) volume. Moreover, if G has an X ×Y × Z straight-line drawing then G has track-number tn(G) ≤ 2XY .

Fig. 2 :

 2 Fig. 2: An edge-maximal (3, 2)-track layout.

Lemma 7 .

 7 track layout of a graph G with maximum partial span s. Then (a) tn 2k (G) ≤ (s + 1)b, and (b) tn k (G) ≤ (2s + 1)b. The next special case is Lemma 6 with b = 1. Lemma 7(b) with k = 1 was proved by Dujmović et al. [26]. 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.

Fig. 3 :

 3 Fig. 3: Illustration to show that every edge of G crosses at most one edge of P.

Fig. 4 :

 4 Fig. 4: Construction of an 8-track refinement of a (2, 2)-track layout.

for k = 1 . 13 .Fig. 5 :

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

Corollary 7 .

 7 Theorem 11 and (1) imply: Every 1-queue graph G has acyclic chromatic number χ a (G) ≤ 4.

Corollary 8 .Corollary 9 .

 89 Every q-queue c-colourable graph G has geometric thickness θ(G) ≤ 2q⌈ c 2 ⌉⌊ c 2 ⌋. Theorem 12 and Corollary 4 imply: Geometric thickness is bounded by queue-number. In particular, every graph G has geometric thickness θ(G) ≤ 8 qn(G)3 .

Lemma 21 .

 21 Let {V i : 1 ≤ i ≤ c} be a vertex vertex c-colouring of a graph G such that each bichromatic subgraph G[V i ,V j ] has acyclic chromatic number at most k. Then G has acyclic chromatic number χ a (G) ≤ c • k c-1 .

Fig. 7 :

 7 Fig. 7: Construction of a track layout of an outerplanar graph in Lemma 22.

Fig. 8 :Theorem 13 .Corollary 10 .

 81310 Fig. 8: The graph G in Lemma 24.

  Tab. 1: Upper bounds on the track-number.

	graph family	track-number	reference
	n vertices	n	trivial
	m edges m edges, max. degree ∆	15m 2/3 14 √ ∆m	Dujmović and Wood [28] Dujmović and Wood [28]
	no K h -minor

  ∈ A. For all edges vw, xy of G[A, B], say vw xy if v ≤ x in A and w ≤ y in B. Clearly is a partial order on

	any two tracks A, B
	Lemma 2. A t-track assignment A of a graph G can be extended into a (k,t)-track layout if and only if
	A has no crossing (k + 1)-tuple.
	Proof. Suppose that A has a crossing (k + 1)-tuple S. Each edge in S must receive a distinct colour. Thus
	A cannot be extended into a (k,t)-track layout. Now suppose A has no crossing (k + 1)-tuple. Consider

  Lemma 12. Every (k, 2)-track layout can be refined to an (edge-monochromatic) 2 • 4 ( k 2 ) -track layout, with 4 ( k 2 ) tracks arising from each of the two given tracks. Proof. Let {A, B} be the tracks and let {E 1 , E 2 , . . . , E k } be the edge colouring in a (k, 2)-track layout of a graph G. By Lemma 11, for each pair {i, j} ∈ [k] 2 , there is an 8-track layout {X

	i, j α ,Y α i, j

Dujmović was supported by FCAR and NSERC. The research of D. Wood was partially supported by NSERC. The research of A. Por and D. Wood was partially completed at the Department of Applied Mathematics and the Institute for Theoretical Computer Science, Charles University, by project LN00A056 of the Ministry of Education of the Czech Republic, and by the European Union Research Training Network COMBSTRU (Combinatorial

Lemma 16. Let σ be a vertex ordering of a graph G. Let {V i : 1 ≤ i ≤ c} be a vertex colouring of G. For all 1 ≤ i, j ≤ c, a pair of edges vw, xy ∈ E(G[V i ,V j ]) form an X-crossing in the track assignment {(V i , σ) : 1 ≤ i ≤ c} if and only if:

• vw and xy are nested in σ (Figures 6(a)-(b)), or

• vw and xy cross in σ with v < σ y < σ w < σ x, and v, x ∈ V i and w, y ∈ V j (Figure 6(e)). Proof. Let σ = (v 0 , v 1 , . . . , v n-1 ) be a vertex ordering of G with band-width b = bw(G). For each 0 ≤ ℓ ≤ b, let V ℓ = {v i : i ≡ ℓ mod (b + 1)}. Not only is {V ℓ : 0 ≤ ℓ ≤ b} a vertex colouring of G, but for every edge vw, if there is a vertex x with v < σ x < σ w, then all three vertices are in distinct colour classes. Thus, it follows from Lemma 16 that with each V ℓ ordered by σ, there is no X-crossing.

Note that Lemma 17 is in fact weaker than the bound due to Dujmović et al. [START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF] that track-number is at most one more than the path-width. However, we consider that this particularly simple proof deserves mention. The following observation is implicit in Lemma 5.3 of Dujmović et al. [START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF].

Lemma 18. For every vertex colouring {V

Planar Graphs

Whether planar graphs have bounded track-number is probably the most important open problem in the field. A crossing-free drawing of a graph in the plane in which all the vertices are on the boundary of the outerface is called outerplanar. A graph is outerplanar if it has an outerplanar drawing. In this section we prove bounds on the track-number of outerplanar graphs, and prove the best known lower bound on the track-number of planar graphs.

Lemma 22.

Every outerplanar graph has a 5-track layout.

Proof. We proceed by induction on n with the following hypothesis: Every maximal outerplanar graph G on n ≥ 2 vertices has a straight-line outerplanar drawing (in which the coordinates of each vertex v are denoted by (X(v),Y (v))) such that:

• the boundary of the drawing is a strictly monotone polygon; that is, every vertical line intersects the boundary in at most two places.

The result will follow since this drawing obviously defines a track layout of G with span two, which can be wrapped onto five tracks by Lemma 7(b). The basis of the induction with n = 2 is trivial. Every maximal outerplanar graph on n ≥ 3 vertices has a vertex v that is adjacent to exactly two vertices u and w, such that uw is an edge on the boundary. Let G ′ = G \ v. Then G ′ is also maximal outerplanar. By induction, G ′ has the desired drawing. The upper envelope of the drawing is the portion of the boundary that is visible from (0, +∞), and the lower envelope of the drawing is the portion of the boundary that is visible from (0, -∞). By the third invariant, every edge that is on the boundary of the drawing is on the upper or lower envelope. Without loss of generality Y (u) < Y (w). As illustrated in Figure 7 We now consider lower bounds on the track-number of outerplanar and planar graphs.

Lemma 23.

There is an outerplanar graph H with track-number tn(H) ≥ 4.

Proof. Let H 1 , H 2 , . . . , H 5 be copies of K 3 . Nominate a vertex w j of each H j . Construct H by adding an additional vertex v adjacent to each w j . Clearly H is outerplanar. Suppose that tn(H) ≤ 3. Without loss of generality, v is in track 1. Thus {w 1 , w 2 , w 3 , w 4 , w 5 } are in tracks 2 and 3. Hence there are three w j vertices in a single track. Without loss of generality, w 1 < w 2 < w 3 in track 2. One vertex x of H 2 is in track 1, since H 2 = K 3 . But this implies that w 2 x forms an X-crossing with w 1 v or w 3 v. Hence tn(H) ≥ 4.

Whether every outerplanar graph has a 4-track layout is an interesting open problem. We conjecture that a large enough outerplanar graph whose weak dual is the 'cubic' tree has track-number 5.