Transforming Stacks into Queues:
Mixed and Separated Layouts of Graphs

Given a vertex order $\sigma$, two edges $(u,v)$ and $(x,y)$ in $E$ are said to cross in $\sigma$ if any order of their endvertices symmetric to is prescribed by $\sigma$. Roughly speaking, for the stack number of $G$, we want a vertex order $\sigma$ in which not many edges pairwise cross. Formally, for an integer $s\ge 1$, an $s$-stack layout of $G=(V,E)$ is a total order $\sigma$ of $V$ together with a partition of $E$ into subsets $E_1,\mathrm{\dots },E_s$, called stacks, such that no two edges in the same stack cross. The minimum number $s$ of stacks needed for a stack layout of graph $G$ is called its stack number and denoted by $\mathrm{sn}(G)$. Stack numbers were first investigated by Bernhart and Kainen [6] in 1979, building on Kainen and Ollman [20, 24]²²2We remark that $s$-stack layouts are also known as $s$-page book embeddings, where stacks are then called pages. Similarly, the stack number $\mathrm{sn}(G)$ is sometimes called the book thickness or page number of $G$..

As a concept “dual” to $s$-stack layouts, for an integer $q\ge 1$, a $q$-queue layout of $G=(V,E)$ is a total order $\sigma$ of $V$ together with a partition of $E$ into subsets $E_1,\mathrm{\dots },E_q$, called queues, such that no two edges in the same queue nest; that is, there are no edges $(u,v)$ and $(x,y)$ in a queue with (or any symmetric order). The minimum number $q$ of queues needed for a queue layout of graph $G$ is called its queue number and denoted by $\mathrm{qn}(G)$. Queue numbers were introduced by Heath and Rosenberg [18] in 1992.

Stack and queue layouts are generalized through the notion of a mixed layout. For integers $s,q\ge 1$, an $s$-stack $q$-queue layout of $G=(V,E)$ is a total order $\sigma$ of $V$ together with a partition of $E$ into $s$ stacks and $q$ queues. The minimum value of $s+q$ needed for an $s$-stack $q$-queue layout of graph $G$ is called its mixed number and denoted by $\mathrm{mn}(G)$. Mixed layouts were already considered by Heath and Rosenberg [18] in 1992, while a thorough study started only recently [26, 22, 16]. In contrast to mixed layouts, we call a layout pure if only stacks or only queues are being used.

Besides their similar definitions, there are more similarities between $k$-stack graphs, $k$-queue graphs, and $k$-mixed graphs, where a $k$-(stack, queue, mixed) graph is defined as a graph admitting a $k$-(stack, queue, mixed) layout. For example, in each case we have sparse graphs with only $𝒪(kn)$ edges for $n$ vertices [6, 18, 25]. Moreover, stack, queue, and mixed numbers are all bounded for planar graphs [8, 14, 5, 30] and for bounded treewidth graphs [1, 28, 9, 15]. On the other hand, neither stack nor queue number is bounded for $3$-regular graphs [29, 3]. Already in 1992, Heath, Leighton, and Rosenberg [17] investigated the relationship between stack and queue layouts; in particular whether stack layouts and queue layouts can be transformed into each other. They introduced the following fundamental question, which remains unanswered despite a wealth of studies on linear graph layouts.

We emphasize that a companion question (“do graphs with bounded queue number have bounded stack number?”) has been recently resolved in the negative by Dujmović et al. [7]. One attempt to resolve Open Problem 1 was made by Dujmović and Wood [11] who showed that the problem is equivalent to the question of whether bipartite $3$-stack graphs have bounded queue number. Note that $1$-stack graphs and $2$-stack graphs are planar, and hence, they have a bounded queue number [8], but the question remains open for $3$-stack graphs.

Turning to mixed layouts, it follows from the definition of the mixed number that for every graph $G$ we have $\mathrm{mn}(G)\le \mathrm{sn}(G)$ and $\mathrm{mn}(G)\le \mathrm{qn}(G)$. However for some graphs $G$, their mixed number $\mathrm{mn}(G)$ is strictly less than $\mathrm{sn}(G)$ and $\mathrm{qn}(G)$; for example, for the complete graph $K_6$ it holds that $\mathrm{sn}(K_6)=\mathrm{qn}(K_6)=3$ but $\mathrm{mn}(K_6)=2$, as illustrated in Figure 1. In particular, graphs with bounded mixed number potentially form a strictly larger class than those of bounded stack number. Thus, the following problem of Alam et al. [22] asks for something (potentially) stronger than Open Problem 1.

As one of our results (cf. Theorem 4), we shall show that Open Problems 1 and 2 are in fact equivalent. That is, either both questions have a Yes-answer or both have a No-answer. In that sense, it is easier to prove a No-answer by finding graphs of unbounded queue number but bounded mixed number (instead of bounded stack number). As a second result, also in Theorem 4, we shall prove that it indeed suffices to look for graphs of mixed number $2$; specifically, graphs that admit $1$-stack $1$-queue layouts. That is, Open Problems 1 and 2 have a Yes-answer if and only if all $1$-stack $1$-queue graphs have bounded queue number.

Since Open Problems 1 and 2 are likely very challenging in their full generality, we investigate a special case for separated mixed layouts of bipartite graphs. A vertex order $\sigma$ of a bipartite graph $G$ with bipartition³³3$(A,B)$ is a bipartition if $A\cap B=\mathrm{\varnothing }$, $A\cup B=V$, and both induced subgraph $G[A],G[B]$ are edgeless. $(A,B)$ is separated if all vertices in $A$ precede all vertices in $B$ (or vice versa). This naturally gives rise to separated $k$-stack, separated $k$-queue, and separated $s$-stack $q$-queue layouts of bipartite graphs $G$, as well as the corresponding separated stack number $\overline{\mathrm{sn}}(G)$, separated queue number $\overline{\mathrm{qn}}(G)$, and separated mixed number $\overline{\mathrm{mn}}(G)$.

Observe that a separated $s$-stack $q$-queue layout can be transformed into a separated $q$-stack $s$-queue layout by reversing the vertex order of one of the parts. It follows that $\overline{\mathrm{sn}}(G)=\overline{\mathrm{qn}}(G)$ for every bipartite graph $G$. Furthermore, every separated vertex order $\sigma$ of $G=(V,E)$ with bipartition $(A,B)$ induces an injective mapping of the edges of $G$ to points of the $|A|\times |B|$ integer grid; see Figure 2. This grid is sometimes referred to as a reduced adjacency matrix of $G$. One can easily verify that a subset $S\subseteq E$ of edges forms a queue (resp. a stack) if and only if the corresponding points form a monotonically increasing (resp. decreasing) subset in the $|A|\times |B|$ grid. The stack-queue transformation mentioned above then corresponds to mirroring the grid along the $x$-axis or along the $y$-axis.

This separated setting has been widely studied (sometimes, implicitly) under different names, such as 2-track layouts [10, 27] or 2-layer drawings [23, 2, 12]. For the present paper, let us introduce the following special variant of Open Problem 2.

We make progress towards the resolution of Open Problems 1 and 2, as well as our new Open Problem 3. Each of these problems asks whether graphs with low stack number (Open Problem 1), low mixed number (Open Problem 2), or low separated mixed number (Open Problem 3) have also low queue number. Formally, we say that the queue number is bounded by stack number (similarly, bounded by mixed number, and bounded by separated mixed number) if for every graph $G$ with stack number $\mathrm{sn}(G)$ and queue number $\mathrm{qn}(G)$, it holds that $\mathrm{qn}(G)\le f(\mathrm{sn}(G))$ for some function $f$ (independent of $G$). The question of whether such functions, $f$, exist are Open Problems 1, 2, and 3.

Clearly, a function $f$ that bounds the queue number in terms of the stack number exists if and only if for all $k\in \mathbb{N}$ there is a constant $C=C_k$ such that every $k$-stack graph has queue number at most $C$. Surprisingly, it is enough to consider just one particular value for $k$. In fact, Dujmović and Wood [11] show that Open Problem 1 is equivalent to the existence of a constant $C$ such that every $3$-stack graph has queue number at most $C$. (It is known that $1$-stack and $2$-stack graphs have queue number at most $2$ [17] and at most $42$ [4], respectively.)

Here, we extend the list to four equivalent statements, showing in particular that Open Problems 1 and 2 are equivalent, and that it is enough to consider $1$-stack $1$-queue graphs.

Turning to separated layouts of (necessarily bipartite) graphs, our main contribution is also a list of four equivalent statements, one of which, namely (1), is Open Problem 3. Statements (3) and (4) show that it is enough to consider $1$-stack $q$-queue graphs, respectively even only $1$-stack $6$-queue graphs, for solving Open Problem 3. Additionally, we discuss a natural approach for Open Problem 3 where we start with the grid representation of a separated $s$-stack $q$-queue layout, and then permute the rows and columns so as to obtain a separated $f(s,q)$-queue layout. Another surprising contribution is that it is always enough to apply the same permutation to the rows and the columns, which is statement (2).

Finally, let us discuss the connections between non-separated and separated layouts. Standard techniques for queue layouts (which we present in Section 2) easily give that Open Problem 2 implies Open Problem 3. In fact, Corollary 7 states that for every bipartite graph $G$ we have $\overline{\mathrm{qn}}(G)\le 2\mathrm{qn}(G)$. However, it remains open whether Open Problem 3 implies Open Problem 2 (or equivalently Open Problem 1). The situation is summarized in Figure 3.

We show that every queue $Q\subseteq E$ for $\sigma$ can be split into $k^2$ queues for ${\sigma }^{\prime }$; see Figure 4(a). Overall, this results in the desired $k^2\cdot q$-queue layout. For $i,j\in [k]$ let $E_{i,j}\subseteq Q$ contain all edges $(u,v)\in Q$ such that and $u\in V_i$ and $v\in V_j$. This partitions $Q$ into $k^2$ many edge sets $E_{i,j}$, and we claim that each $E_{i,j}$ is a queue for ${\sigma }^{\prime }$. For $i=j$, the relative order of any $u,v\in V_i$ is unchanged in ${\sigma }^{\prime }$, and hence $E_{i,i}$ is a queue for ${\sigma }^{\prime }$. For $i\ne j$, let $e_1=(u_1,v_1)$ and $e_2=(u_2,v_2)$ be two edges in $E_{i,j}$ with $u_1,u_2\in V_i$ and $v_1,v_2\in V_j$. Without loss of generality assume that (hence ) and assume for a contradiction that $e_1$ nests $e_2$ in ${\sigma }^{\prime }$, that is, or . In either case, it follows that and hence . Together with (as $(u_2,v_2)\in E_{i,j}$) this yields and $e_1$ nests $e_2$ in $\sigma$ – a contradiction to $Q$ being a queue. It follows that each $E_{i,j}$ requires at most one queue in the layout with vertex order ${\sigma }^{\prime }$, which concludes the first case of the proof.

In the bipartite case, for each queue $Q$ in the original layout, let $e=(u,v)$ be an edge in $Q$ with $u\in V_i$ with $i\le \mathrm{\ell }$ and $v\in V_j$ with . As there are $\mathrm{\ell }\cdot (k-\mathrm{\ell })$ combinations of $i$ and $j$, and we require two queues, namely $E_{i,j}$ and $E_{j,i}$, for each combination, the resulting layout with vertex order ${\sigma }^{\prime }$ requires $2\cdot \mathrm{\ell }\cdot (k-\mathrm{\ell })\cdot q$-queues in total. $◀$

Applying the lemma to bipartite graphs with $\mathrm{\ell }=1$ and $k=2$ such that $V_1=A$ and $V_2=B$ yields the following (well-known) fact; see [25] for an alternative proof.

The next two results concern graph subdivisions. A subdivision of a graph $G$ is a graph obtained from $G$ by replacing each edge $(u,v)$ in $G$ by a path with one or more edges. Internal vertices on such a path are called division vertices.

A converse operation to a subdivision is a (path-)contraction. We use a more general transformation here. An r-shallow minor is a restricted form of a graph minor in which each (connected) subgraph that is contracted to form the minor has radius at most $r$, where the radius is defined as the minimum of the eccentricities of its vertices. For an $s$-stack $q$-queue graph $G$, we will combine the following result with finding an $s^{\prime }$-stack $q^{\prime }$-queue subdivision $H$ where $s^{\prime }\le s$ and $q^{\prime }\le q$, which has $G$ as an $r$-shallow minor in order to prove equivalence statements in Theorem 4 and Theorem 5.

First we show how to obtain a tree-layout for an $s$-stack $q$-queue graph $G=(V,E)$ with the vertex order $\sigma$. Denote $h=\lceil {\log }_2(\max (s,q))\rceil$ so that $\max (s,q)\le 2^h$. Assume that $E=S_1\cup \mathrm{\cdots }\cup S_s\cup Q_1\cup \mathrm{\cdots }\cup Q_q$, where $S_i,1\le i\le s$ are stacks and $Q_i,1\le i\le q$ are queues.

Consider the subgraph of $G$ induced by all stack edges, $G^s=(V,S_1\cup \mathrm{\cdots }\cup S_s)$. Let $T_s$ be a binary tree of height $h+1$ in which the root node has a single child, each internal non-root node has exactly two children, and all leaves are at the same depth. By Lemma 10, there exists a subdivision of $G^s$, denoted $D^s$, with exactly $2(h+1)$ division vertices per edge and a simple $T_s$-layout of $D^s$. It holds that $𝒮(x)=1,𝒬(x)=0$ for $x\in \tilde{V}(T_s)$, $𝒮(x)=𝒬(x)=0$ for $x\in V(T_s)\setminus \tilde{V}(T_s)$, and $𝒦(x,y)=1$ for $(x,y)\in E(T_s)$; see Figure 5.

Next consider the subgraph of $G$ induced by the queue edges, $G^q=(V,Q_1\cup \mathrm{\cdots }\cup Q_q)$. Start with a binary tree of height $h+1$, denoted $T_q^{\prime }$, which is a copy of $T_s$ (that is, the root node has one child and each internal non-root node has two children). There exists a subdivision of $G^q$ with exactly $2h+2$ subdivision vertices and its simple $T_q^{\prime }$-layout by Lemma 10. We modify the subdivision and the tree-layout as follows. Consider a leaf node $x^{\prime }\in \tilde{V}(T_q^{\prime })$ and let $G_{x^{\prime }}$ be the graph induced by vertices in $T_{x^{\prime }}$ and the corresponding intra-bag edges. Observe that $𝒬(x^{\prime })=1$ in the $T_q^{\prime }$-layout, and hence, $\mathrm{qn}(G_{x^{\prime }})=1$ with as the vertex order. Now, we apply Lemma 8 by subdividing every edge of $G_{x^{\prime }}$ once and let $G_x$ be the resulting graph. This results in a $2$-queue layout of the subdivision $G_x$ in which the vertices of $G_{x^{\prime }}$ are separated from the new division vertices and are ordered as in the $T_q^{\prime }$-layout. Thus, we can build a new tree, denoted $T_q$, by appending a child, $x$, to every node $x^{\prime }\in \tilde{V}(T_q^{\prime })$. This results in a (non-simple) $T_q$-layout for $G_q$, where the leaf nodes of $T_q$ contain the division vertices in the order given by Lemma 8. Since the queue number of $G_x$ is at most $2$, the inter-bag edges between $G_{x^{\prime }}$ and $G_x$ can be partitioned into two sets of pairwise non-crossing edges, i.e., we have that $𝒦(x^{\prime },x)=2$ for all $(x^{\prime },x)\in E(T_q)$, where $x\in \tilde{V}(T_q)$; see Figure 5(a) for an illustration.

By Lemma 10, the root bags of the $T_s$-layout and the $T_q$-layout contain the same vertices, $V$, both ordered by $\sigma$. Thus, we can merge the two tree-layouts into a joint one, called $T_{sq}$-layout; see Figure 5(b). The corresponding subdivision of $G$, denoted $D^{sq}$, has stack edges subdivided $2h+2$ times and queue edges subdivided $2h+3$ times. To apply Lemma 11 for the $T_{sq}$-layout, we color all the edges of $T_{sq}$ blue and find a $1$-stack layout of the tree via a depth-first search traversal such that every node precedes its children in the order. Let us argue that the result of applying Lemma 11 is a $3$-stack layout, that is, ${\lambda }_s=3$ and ${\lambda }_q=0$.

Note that $𝒬(x)=0$ for all nodes of $T_{sq}$ and the tree contains no red edges; thus, ${\lambda }_q=0$. For the stack number, consider four disjoint groups of nodes of $T_{sq}$:

• $\mathrm{■}$

  for $x\in \tilde{V}(T_s)$, it holds that $𝒮(x)=1$ and $𝒦(y,x)=1$ for $(y,x)\in E^s$;

• $\mathrm{■}$

  for $x\in V(T_s)\setminus \tilde{V}(T_s)$ and $x\in V(T_q^{\prime })\setminus \tilde{V}(T_q^{\prime })$, it holds that $𝒮(x)=0$, there exists one edge $(y,x)\in E^s$ with $𝒦(y,x)=1$ and two edges $(x,y)\in E^s$ with $𝒦(x,y)=1$;

• $\mathrm{■}$

  for $x\in \tilde{V}(T_q^{\prime })$, it holds that $𝒮(x)=0$, $𝒦(y,x)=1$ for a single edge $(y,x)\in E^s$, and $𝒦(x,y)=2$ for a single edge $(x,y)\in E^s$;

• $\mathrm{■}$

  for $x\in \tilde{V}(T_q)$, it holds that $𝒮(x)=0$, and $𝒦(y,x)=2$ for a single edge $(y,x)\in E^s$.

Combining everything together, we get

Therefore, subdivision $D^{sq}$ of $G$ admits a $3$-stack layout by Lemma 11. $◀$

With a similar technique we can find a $1$-stack $1$-queue subdivision (Lemma 13) instead of a $3$-stack subdivision (Lemma 12). The proof of the next result is given in [21].

We now prove Theorem 4, in particular that Open Problems 1 and 2 are equivalent.

See 4

It is immediate that (4) implies (1), (2), and (3). That (1)$\iff$(2) is proven by Dujmović and Wood [11].

Now we show that (2) $\Rightarrow$ (4). Assume that every $3$-stack graph has a bounded queue number, $C\in 𝒪(1)$. Let $G$ be an $s$-stack $q$-queue graph. By Lemma 12, $G$ admits a $3$-stack subdivision, $D$, with at most $k=2\lceil {\log }_2(\max (s,q))\rceil +3$ division vertices per edge. By the assumption, $\mathrm{qn}(D)\le C$. Note that $G$ is an $r$-shallow minor of $D$ for $r=(k+1)/2=\lceil {\log }_2(\max (s,q))\rceil +2$. By Lemma 9, we get

which proves that $G$ has a bounded queue number, as long as $s,q$ and $C$ are constants.

Similarly we show that (3) $\Rightarrow$ (4). Suppose that every $1$-stack $1$-queue graph has queue number at most $C\in 𝒪(1)$. Let $G$ be an $s$-stack $q$-queue graph. By Lemma 13, $G$ admits a $1$-stack $1$-queue subdivision, $D$, with $k=4\lceil {\log }_2(\max (s,q))\rceil +6$ division vertices per edge. By the assumption, $\mathrm{qn}(D)\le C$, and $G$ is an $r$-shallow minor of $D$ for $r=\lceil (k+1)/2\rceil$. Again by Lemma 9, we get

which shows that $G$ has a bounded queue number, as long as $s,q$ and $C$ are constants. $◀$

Let $G=(V,E)$ be a bipartite graph with bipartition $(A,B)$ admitting a separated $1$-stack $1$-queue layout with vertex order $\sigma$. Consider the reduced adjacency matrix $M$ with columns $A=(a_1,\mathrm{\dots },a_m)$ and rows $B=(b_1,\mathrm{\dots },b_n)$ ordered according to $\sigma$. The edges $S\subset E$ in the stack form a monotonically weakly decreasing subset of $|A|\times |B|$. The edges $Q\subset E$ in the queue form a monotonically weakly increasing subset of $|A|\times |B|$. Without loss of generality we can assume (by adding edges to the graph) that $S$ and $Q$ correspond to inclusion-maximal such subsets; see Figure 6.

Let $(a_i,b_j)\in A\times B$ be a point/edge that is contained in both, $S$ and $Q$. Now consider the vertex order $a_i,\mathrm{\dots },a_1,a_{i+1},\mathrm{\dots },a_m$ of the columns obtained by reversing the order of $a_1,\mathrm{\dots },a_i$. Similarly, consider the vertex order $b_j,\mathrm{\dots },b_1,b_{j+1},\mathrm{\dots },b_n$ of the rows obtained by reversing the order of $b_1,\mathrm{\dots },b_j$. Let ${\sigma }^{\prime }$ denote the resulting separated vertex order of $G$. Now the edges in $Q$ incident to $a_1,\mathrm{\dots },a_i$ form a queue $Q_1$ in ${\sigma }^{\prime }$. Also the remaining edges in $Q$, incident to $a_{i+1},\mathrm{\dots },a_m$ form a queue $Q_2$ in ${\sigma }^{\prime }$. Similarly, the edges in $S$ incident to $b_1,\mathrm{\dots },b_j$ form a queue $Q_3$ in ${\sigma }^{\prime }$. Also the remaining edges in $S$, incident to $b_{j+1},\mathrm{\dots },b_m$ form a queue $Q_4$ in ${\sigma }^{\prime }$; see again Figure 6. This is a separated $4$-queue layout of $G$. $◀$

Note that by applying 14, separated $1$-stack $1$-queue graphs also admit a separated $4$-stack layout. However, we do not know whether the bound of $4$ in Theorem 15 is best-possible and remark that $K_{3,3}$ admits a separated $1$-stack $1$-queue layout but its separated stack/queue number is $3$.

The simple operation of reversing the order of some consecutive vertices can be employed in a “checkerboard” fashion. Consider a given separated mixed layout (e.g., with $s$ stacks and $q$ queues). Assume we have partitioned the reduced adjacency matrix by means of a superimposed grid with a checkerboard odd-even pattern, in such a way that odd grid cells contain no stack edges and even grid cells contain no queue edges. Then, the vertex order of every second row and column can be reversed to derive a separated pure queue layout. Finding such a grid refinement is always possible, that is, down to individual rows and columns, however the derived $\overline{\mathrm{sn}}$ and $\overline{\mathrm{qn}}$ are dependent on the grid granularity and thus may not be bounded by $\overline{\mathrm{mn}}$. An example for specific separated $s$-stack $q$-queue layouts with bounded $\overline{\mathrm{qn}}$ number are grids where each cell contains either an increasing or decreasing diagonal. In this case, grid columns and rows can be halved in order to apply the checkerboard approach; see Figure 7.

However there exist graphs, where such operations do not suffice and more involved row and column permutations are necessary. In [21] we provide as a challenging example a subcubic bipartite graph that admits a separated $1$-stack $2$-queue layout and a fairly simple $4$-queue pure layout. However, the grid granularity has to be super-constant in order to transform the mixed into the pure layout. We conclude that even for low-degree graphs with $\overline{\mathrm{mn}}(G)=3$, it is not obvious how to transform a separated mixed layout into a separated pure layout, say with few queues.

While we do not know how to generalize Theorem 15 even just to separated $1$-stack $2$-queue layouts, we can narrow down the difficult case of Open Problem 3. If Open Problem 3 is answered positively, we can find an $f(s,q)$-queue layout for any bipartite graph admitting a separated $s$-stack $q$-queue layout. In Theorem 5 we show three equivalent formulations of this problem. In the challenging example presented in our preprint [21], the transformation from the separated mixed to the separated pure layout applies the same column and row permutation. Now, Theorem 5 states that we may always assume that rows and columns are identically permuted when transforming a separated mixed layout into a separated pure layout.

Further, we show in Lemma 17 that every separated $s$-stack $q$-queue layout can be transformed into a separated $1$-stack $f(s,q)$-queue layout, while this transformation does not change the separated queue number by too much. This implies that one can restrict the attention to separated $1$-stack $q$-queue layouts, for solving Open Problem 3.

See 5

Observe that (1) immediately implies (3), which implies (4). That (2) implies (1) is also immediate, when adding isolated vertices to guarantee $|A|=|B|$. The proofs of the other directions are deferred, in particular see Lemma 16 for (1) $\Rightarrow$ (2) and Lemma 17 for (3) $\Rightarrow$ (1). For (4), we show equivalence by proving that (4) implies (3) in Lemma 18. $◀$

In other words, Lemma 16 proves that (1) implies (2) in Theorem 5.

Let $u_1,\mathrm{\dots },u_n$ and $v_1,\mathrm{\dots },v_n$ be the order of $A$ and $B$ in the given separated $s$-stack $q$-queue layout of $G$. We add the “identity” queue $Q$, where for each $i$, $1\le i\le n$, there is the edge $(u_i,v_i)$ (if not already present in $G$). Let $G^{\prime }=(A\cup B,E\cup Q)$ be the resulting bipartite graph. By assumption, there exists a separated $f(s,q+1)$-queue layout of $G^{\prime }$ with vertex order ${\sigma }_0$. We are looking for another vertex order $\sigma$ such that, compared to the initial order, $A$ and $B$ are permuted the same, that is, the columns and rows in the reduced adjacency matrix are identically permuted. Since we added the identity queue $Q$ to obtain $G^{\prime }$ in the beginning, this is equivalent to restoring $Q$ to the diagonal in the matrix; see Figure 8.

To that end, we shall apply Lemma 6 to change only the order of vertices in $A$, which corresponds to permuting the columns in the matrix. Let $k=f(s,q+1)$ and $E_1,\mathrm{\dots },E_k$ be the queues in the $f(s,q+1)$-queue layout of $G^{\prime }$ and $A_i=\{u\in A\mid (u,v)\in Q\cap E_i\}$, $1\le i\le k$. We want to apply the Riffle-Lemma (Lemma 6-(2)) with the partition of $V$ into $A_1,\mathrm{\dots },A_k$ and $B$. To this end, we keep the order of $B$ (the rows), and restore $Q$ as a diagonal by simply sorting the columns according to their row in $Q$. Since each $E_i$ is a queue, the relative order within each $A_i$ is kept intact, as required by Lemma 6. Hence, by Lemma 6-(2), the resulting layout has at most $2\cdot f(s,q+1)\cdot f(s,q+1)$ queues in total. $◀$

If (3) of Theorem 5 holds, then the separated $1$-stack $(s+q-1)$-queue layout of $H$ has bounded queue number, i.e, $\mathrm{qn}(G)\in 𝒪(\mathrm{qn}{(H)}^3)\le f(s+q-1)$ for some function $f$. Hence $\mathrm{qn}(G)\le f^{\prime }(s,q)=f(s+q-1)$, implying (1) of Theorem 5.

Assume we have a bipartite graph $G$, that admits a separated $s$-stack $q$-queue layout. We will build a new bipartite graph $H$, such that $H$ has a separated $1$-stack $(s+q-1)$-queue layout. We will then show that for the separated queue numbers of $G$ and $H$, it holds that $\mathrm{qn}(G)\in 𝒪(\mathrm{qn}{(H)}^3)$. That is, a small queue number of $H$ implies a small queue number of $G$. Next we make the argument formal.

Let $G=(A\cup B,E),|A|=n,|B|=m$, $S_1,\mathrm{\dots },S_s$ be the stacks and $Q_1,\mathrm{\dots },Q_q$ be the queues in the separated $s$-stack $q$-queue layout. We build $H$ as follows. The vertices of $H$ are $A\cup ({\bigcup }_k{U}^k)\cup B\cup ({\bigcup }_k{V}^k)$, where $A=\{a_1,\mathrm{\dots },a_n\}$ and $B=\{b_1,\mathrm{\dots },b_m\}$ are copied from $G$, while $U^k\subseteq \{u_1^k,\mathrm{\dots },u_n^k\}$ and $V^k\subseteq \{v_1^k,\mathrm{\dots },v_m^k\}$ for any $1\le k\le s-1$ are new. $U^k$ contains a vertex $u_i^k$ for each vertex $a_i$ incident to an edge $(a_i,b_j)\in S_k$. Likewise, $V^k$ contains a vertex $v_j^k$ for each such $b_j$. Vertices in $A$ and $B$ that are not incident to an edge in $S_k$ are omitted in $U^k$ and $V^k$. (Note that for each stack $S_k$, the new vertices in $U^k$ and $V^k$ are added to construct parts of the graph $H$ starting from $G$, while the last stack $S_s$ is left as is.) In the reduced adjacency matrix of $H$, the new vertices are represented by additional blocks of $n_k$ consecutive rows for each $U^k$ and $m_k$ consecutive columns for each $V^k$, where $n_k$ ($m_k$) is the number of vertices of $A$ ($B$) having an edge in $S_k$. Row blocks of $U^k$ and column blocks of $V_k$ are subsequent for $k=1,\mathrm{\dots },s-1$. Intuitively, we move the stack $S_k$ from $A\times B$ to $U^k\times V^k$, $k=1,\mathrm{\dots },s-1$. We leave the last stack $S_s$ with all $q$ initial queues in $A\times B$. Finally, we put one new queue each in $A\times U^k$ and $V^k\times B$, $k=1,\mathrm{\dots },s-1$. Figure 10 shows the construction and in particular the order of the rows $U^1,\mathrm{\dots },U^{s-1}$ and columns $V^1,\mathrm{\dots },V^{s-1}$.

More formally, for every edge $(a_i,b_j)\in Q_1\cup \mathrm{\dots }\cup Q_q$, there is an edge $(a_i,b_j)$ in $H$. For every stack edge, $(a_i,b_j)$ of stack $S_k,1\le k\le s-1$, there are three edges $(a_i,u_i^k),(u_i^k,v_j^k),(v_j^k,b_j)$ in $H$. (In case of multiple edges between a pair of vertices, we keep only one instance.) It is easy to verify that $H$ admits a separated $1$-stack $(s+q-1)$-queue layout, as for every original stack $S_k$, $1\le k\le s-1$ the edges $(a_i,u_i^k)$ and $(v_j^k,b_j)$ for every $(a_i,b_j)\in S_k$ form a queue respectively, due to the increasing column and row indices of each block $U^k$ and $V^K$ starting from the bottom left of the matrix. In fact, edges between vertices in $A$ and $U^k$ and edges between vertices in $B$ and $V^k$ fit in a single queue, since the former lie below and to the left of the latter in the matrix. The original queues remain, yielding $q+s-1$ queues in total. For a stack $S_k$, the edges $(a_i,b_j)\in S_k$ are a decreasing subset in $A\times B$ and due to the increasing ordering of indices in every column and row block of the matrix, the edges $(u_i^k,v_j^k)$ in $U^k\times V^k$ have the same property. The ordering of the row blocks $U^k$ and column blocks $V^k$, where $A\times B$ and $U^k\times V^k$, $1\le k\le s-1$ are positioned diagonally from the top left to the bottom right of the matrix, then allows to combine the $s$ stacks of $G$ into one single stack in $H$.

Finally, we show that $\mathrm{qn}(G)\in 𝒪(\mathrm{qn}{(H)}^3)$. To this end, consider a $\mathrm{qn}(H)$-queue layout of $H$. Now, contract for each $i=1,\mathrm{\dots },n$ the vertex $a_i$ with its neighbors of the form $u_i^k$, $1\le k\le s-1$. Similarly, contract for each $j=1,\mathrm{\dots },m$ the vertex $b_j$ with its neighbors of the form $v_j^k$, $1\le k\le s-1$. The result is a $1$-shallow minor of $H$, and most crucially, the result is exactly the initial graph $G$. Hence, Lemma 9 with radius $r=1$ gives that $\mathrm{qn}(G)\le (2r+1){(2\mathrm{qn}(H))}^{2r+1}=24\cdot \mathrm{qn}{(H)}^3$. $◀$

Using the techniques from Section 3, we can provide the final missing piece of Theorem 5.

In other words, Lemma 18 proves that (4) implies (3) in Theorem 5, as applying Lemma 9 for the $r$-shallow minor $G$ of $D$ with $k=2\lceil {\log }_{2}q\rceil$ and $r=\lceil (k+1)/2\rceil$ implies bounded queue number of $G$ for a function $f(q)$.

Let $G=(V,E_s\cup E_1\cup \mathrm{\cdots }\cup E_q)$ be a bipartite graph that admits a separated $1$-stack $q$-queue layout such that $E_s$ is a stack and $E_i,1\le i\le q$ are queues. Denote $h=\lceil {\log }_{2}q\rceil$ so that $q\le 2^h$. We consider the subgraph of $G$ induced by the queue edges, $G^q=(V,E_1\cup \mathrm{\cdots }\cup E_q)$. Let $T$ be a complete binary tree of height $h$. By Lemma 10, there exists a subdivision of $G^q$, denoted $D^q$, and a simple $T$-layout of $D^q$ in which $𝒮(x)=0,𝒬(x)=1$ for all $x\in \tilde{V}(T)$, $𝒮(x)=𝒬(x)=0$ for all non-leaf nodes $x\in V(T)\setminus \tilde{V}(T)$, and $𝒦(x,y)=1$ for all $(x,y)\in E(T)$. Note that $D^q$ contains exactly $2h$ division vertices per edge and it is bipartite; see Figure 11.

Now, color all edges of $T$ red and find a $1$-queue layout of $T$ via a breadth-first search traversal such that every node precedes its children in the order. By Lemma 11 applied to graph $G^q$ and its simple $T$-layout, we obtain a linear layout of $D^q$. Let us argue that this result is in fact a $3$-queue layout of $D^q$, i.e., that ${\lambda }_s=0$ and ${\lambda }_q\le 3$ as defined in Lemma 11. On the one hand, $𝒮(x)=0$ for all the nodes of $T$ and there are no blue edges in $T$. Thus, we have ${\lambda }_s=0$. On the other hand, every node $x\in V(T)$ has at most two outgoing edges in the layout of $T$, i.e., the set $\{(y,z)\in E^q\mid y{\le }_{\sigma }x{\le }_{\sigma }z\}$ contains at most two edges. Hence,

The final step is to convert the $3$-queue layout of $D^q$ into a separated layout. This is accomplished by Corollary 7, which in worst case doubles the number of queues. The transformations of Lemma 11 and Corollary 7 keep the relative order of the original vertices $V$ unchanged. Thus, the resulting layout of $D^q$ can be joined with the stack edges $E_s$ to finally yield a subdivision $D$ of $G$ (in which the stack edges are not subdivided) with a separated $1$-stack $6$-queue layout. $◀$