# On the Deque and Rique Numbers of
Complete and Complete Bipartite Graphs

Michael A. Bekos1, Michael Kaufmann2, Maria Eleni Pavlidi3, Xenia Rieger4,

1Department of Mathematics, University of Ioannina, Ioannina, Greece
<EMAIL_ADDRESS>
2Institute for Computer Science, University of Tübingen, Tübingen, Germany
<EMAIL_ADDRESS>
3Department of Mathematics, University of Ioannina, Ioannina, Greece
<EMAIL_ADDRESS>
4Institute for Computer Science, University of Tübingen, Tübingen, Germany
<EMAIL_ADDRESS>
###### Abstract

Several types of linear layouts of graphs are obtained by leveraging known
data structures; the most notable representatives are the stack and the queue
layouts. In this content, given a data structure, one seeks to specify an
order of the vertices of the graph and a partition of its edges into _pages_ ,
such that the endpoints of the edges assigned to each page can be processed by
the given data structure in the underlying order.

In this paper, we study deque and rique layouts of graphs obtained by
leveraging the double-ended queue and the restricted-input double-ended queue
(or deque and rique, for short), respectively. Hence, they generalize both the
stack and the queue layouts. We focus on complete and complete bipartite
graphs and present bounds on their deque- and rique-numbers, that is, on the
minimum number of pages needed by any of these two types of linear layouts.

##  1 Introduction

Stack and queue layouts form two of the most studied types of linear layouts
of graphs; they date back to 70’s [8, 16] and over the years several
remarkable results have been proposed in the literature [10, 15, 17, 18, 22].
For an introduction, refer to Section 2. Both layouts are defined by an
underlying vertex order and an edge-partition into a certain number of so-
called _pages_ (_stacks_ or _queues_ , respectively), such that when
restricting to a single page the endpoints of the edges assigned to it can be
processed by the corresponding data structure in the order that appears in the
underlying vertex order.

Since given a graph the natural goal is to find a layout of it that minimizes
the number of used pages under the restrictions mentioned above, stack and
queue layouts have naturally been leveraged to estimate the power of the
respective data structures as a mean for representing graphs (for a wealth of
other applications, e.g., to VLSI design and Graph Drawing, refer to [11]).
The well-known _stack-number_ (a.k.a.  _book-thickness_ or _page-number_ in
the literature) of a graph corresponds to the minimum number of stacks
required by any of the stack layouts of it; the queue-number of a graph is
defined symmetrically. In this context, it was recently shown that the stack-
number of a graph cannot always be bounded by its corresponding queue-number
[9], resolving a long-standing open question by Heath, Leighton and Rosenberg
[15]; the other direction is still unknown.

A data structure that generalizes both the stack and the queue is the so-
called _double-ended queue_ or _deque_ , for short.111While in a stack
insertions and removals only occur at its head and in a queue insertions only
occur at its head and removals only at its tail, a deque supports insertions
and removals both at its head and its tail. As a matter of fact, the most
common implementations of stacks and queues are derived by restricting
corresponding implementations of deques. So, in this aspect, one naturally
expects that the corresponding linear layouts that are obtained by employing
the deque data structure for stipulating their edge-partitions will require
fewer pages (called _deques_ in this content) than those of stack or queue
layouts, since, obviously, the latter form a special case of the former.

However, in contrast to the literature for stack and queue layouts, the
corresponding literature for deque layouts is significantly reduced. To the
best of our knowledge, there exists only one work introducing and studying
deque layouts by Auer et al. [3], who provide a complete characterization of
the graphs admitting $1$-deque layouts (that is, deque layouts with a single
deque): a graph admits a $1$-deque layout if and only if it is a spanning
subgraph of a planar graph with a Hamiltonian path; see also [2]. Even though
the _deque-number_ of a graph (that is, the minimum number of deques required
by any of the deque layouts of the graph) has not been explicitly studied so
far in the literature as a graph parameter, from the characterization by Auer
et al. one can easily deduce the following.

######  Observation 1 (Auer et al. [3]).

The deque-number of a graph is at most half of its stack-number.

Note that the queue-number is also a trivial upper bound on the deque-number
of a graph. 1, however, immediately implies improved upper bounds on the
deque-number of several graph classes, e.g., the deque-number of the complete
graph $K_{n}$ is at most $\lceil\frac{n}{4}\rceil$ [8], the deque-number of
the complete graph $K_{n,n}$ is at most $\lceil\frac{\lfloor
2n/3\rfloor+1}{2}\rceil$ [12], while the deque-number of treewidth-$k$ graphs
is at most $\lceil\frac{k+1}{2}\rceil$ [14]. Also, since there exist maximal
planar graphs that do not have a Hamiltonian path (e.g., the $n$-vertex ones
with an independent set of size greater than $\frac{n}{2}+2$), it follows by a
well-known result by Yannakakis [22] that the deque-number of planar graphs is
$2$; see also [6, 23].

Another consequence of 1 is that deque layouts cannot be characterized by
means of forbidden patterns in the underlying linear order, as it is the case,
e.g., for stack and queue layouts [16, 20]; the former do not allow two edges
of the same page to cross (i.e., to have alternating endpoints), while in the
latter no two edges of the same page nest (i.e., have nested endpoints). The
reason for the lack of such a characterization for deque layouts is the fact
that maximal planar graphs with a Hamiltonian path are the maximal graphs that
admit $2$-stack layouts and these layouts do not admit characterizations in
terms of forbidden patterns in the underlying linear order [21]. A
characterization in terms of forbidden patterns is possible, however, for a
special type of deque layouts, which were recently introduced and are referred
to as _rique layouts_ [4], since the underlying data structure is of
restricted input (so-called _restricted-input double-ended queue_ or _rique_
,222Formally, in a rique insertions occur only at the head, and removals occur
both at the head and the tail. Thus, it is a special case of a deque and a
generalization of a stack or of a queue. for short): a graph admits a
$1$-rique layout if and only if it admits a vertex order $\prec$ avoiding
three edges $(a,a^{\prime})$, $(b,b^{\prime})$ and $(c,c^{\prime})$ such that
$a\prec b\prec c\prec b^{\prime}\prec\\{a^{\prime},c^{\prime}\\}$.

### Our contribution.

In this work, we present bounds on the deque- and rique-numbers of complete
and complete bipartite graphs. Especially, for deque layouts, the main
research question that triggered our work is whether it is possible to obtain
better bounds than the obvious ones that one can deduce from 1 (or in other
words, whether the deque data structure is more powerful for representing
graphs than two stacks). Surprisingly enough, we prove that for the case of
complete graphs, this is not the case (see Theorem 3), while for the case of
complete bipartite graphs our upper bound shows that an improvement by a
constant number is possible (to achieve this, however, we describe a rather
complicated edge-to-deques assignment; see Theorem 6). For rique layouts, our
contribution is twofold. First, we improve the upper bound on the rique-number
of $K_{n}$ from $\lceil\frac{n}{3}\rceil$ [4] to $\lfloor\frac{n-1}{3}\rfloor$
(see Theorem 5), which we prove to be tight up to $n=30$ using an SAT-based
approach (see Section 5). We complete our study with an upper bound of
$\lfloor\frac{n-1}{2}\rfloor-1$ on the rique-number of $K_{n,n}$.

##  2 Preliminaries

A _vertex order_ $\prec$ of a graph $G$ is a total order of its vertices, such
that for any two vertices $u$ and $v$ of $G$, $u\prec v$ if and only if $u$
precedes $v$ in the order. We write $[u_{1},\dots,u_{k}]$ if and only if
$u_{i}\prec u_{i+1}$ for all $1\leq i\leq k-1$. Let $F$ be a set of $k\geq 2$
pairwise independent edges $(u_{i},v_{i})$ of $G$, that is,
$F=\\{(u_{i},v_{i});\;i=1,\dots,k\\}$. If the order is
$[u_{1},\dots,u_{k},v_{k},\dots,v_{1}]$, then we say that the edges of $F$
form a _$k$ -rainbow_, while if the order is
$[u_{1},v_{1},\dots,u_{k},v_{k}]$, then the edges of $F$ form a _$k$
-necklace_. The edges of $F$ form a _$k$ -twist_, if the order is
$[u_{1},\dots,u_{k},v_{1},\dots,v_{k}]$; see Fig. 1. Two independent edges
that form a $2$-twist ($2$-rainbow, $2$-necklace) are commonly referred to as
_crossing_ (_nested_ , _disjoint_ , respectively).

(a)

(b)

(c)

(d)

Figure 1: Illustration of: (a) a $3$-rainbow, (b) a $3$-twist, (c) a
$3$-necklace, and (d) a deque.

A _stack_ is a set of pairwise non-crossing edges in $\prec$, while a _queue_
is a set of pairwise non-nested edges in $\prec$. A _rique_ is a set of edges
in which no three edges $(a,a^{\prime})$, $(b,b^{\prime})$ and
$(c,c^{\prime})$ with $a\prec b\prec c\prec
b^{\prime}\prec\\{a^{\prime},c^{\prime}\\}$ exists in $\prec$. A deque is more
difficult to describe due to the absence of a forbidden pattern. A relatively-
simple way is the following. Assume that the vertices of a graph are arranged
on a horizontal line $\ell$ from left to right according to $\prec$ (say,
w.l.o.g., equidistantly). Then, each edge $(v_{i},v_{j})$ with $v_{i}\prec
v_{j}$ can be represented either (i) as a semi-circle that is completely above
or completely below $\ell$ connecting $u_{i}$ and $u_{j}$, or (ii) as two
semi-circles on opposite sides of $\ell$, one that starts at $u_{i}$ and ends
at a point $p_{ij}$ of $\ell$ to the right of the last vertex of $\prec$ and
one that starts at point $p_{ij}$ and ends at $u_{j}$. With these in mind, a
deque is a set of edges each of which can be represented with one of the two
types (i) or (ii) that avoids crossings (such a representation is called
_cylindric_ in [3]); see Fig. 1(d). A deque further allows classifying the
edges into four categories: head-head, tail-tail, head-tail and tail-head;
refer to the blue, light-blue, red and light-red edges of Fig. 1(d),
respectively. A _head-head_ (_tail-tail_) edge is a type-(i) edge drawn above
(below, respectively) $\ell$. Symmetrically, a _head-tail_ (_tail-head_) edge
is a type-(ii) edge whose first part is above (below) $\ell$, while its second
part is below (above, respectively) $\ell$. Given a deque layout $L$ and a set
of edges $E$, we write $E_{x}$ to denote that all edges of $E$ are of type-$x$
in $L$, where $x\in\\{hh,tt,ht,th\\}$.

In view of the above definitions, a rique can be equivalently defined as a
deque without tail-tail and tail-head edges [4]. Also, it is not difficult to
see that the subset of the head-head or tail-tail edges of a deque induce a
stack in $\prec$, while the set of the head-tail or tail-head edges of a deque
induces a queue in $\prec$.

Since we focus on complete and complete bipartite graphs, for representing
their linear layouts we use a convenient way first introduced in [19] and
subsequently used in several works [12, 13, 1]. Let $\prec$ be an order of the
$n$ vertices $v_{1},\dots,v_{n}$ of a graph $G$ such that
$v_{1}\prec\dots\prec v_{n}$. Then, each edge $(v_{i},v_{j})$ of $G$ with
$i<j$ is mapped to point $(i,j)$ of the $n\times n$ grid $H=[1,n]\times[1,n]$.
A set of head-head or tail-tail edges of the same page (deque or rique)
corresponds to a set of points on $H$ whose union forms a monotonically
decreasing curve on $H$ [19]. A set of head-tail or tail-head edges of the
same page (deque or rique) corresponds to a set of points on $H$ whose union
forms a monotonically increasing path on $H$ [1]. If a deque contains head-
tail and tail-head edges, special care is needed to avoid configurations not
appearing in a cylindric layout.

##  3 Complete graphs

In this section, we study the deque- and rique-numbers of the complete graph
$K_{n}$. As already mentioned, 1 implies that $\lceil\frac{n}{4}\rceil$ is an
easy-to-obtain upper bound on the deque-number of $K_{n}$. In the following,
we prove that this bound is tight. To do so, we first give an estimation on
the maximum number of edges that a graph admitting a $k$-deque layout can
have.

######  Lemma 2.

A graph with $n$ vertices admitting a deque layout with $k$ pages has at most
$(2k+1)n-5k-1$ edges.

###### Proof.

Let $G$ be a graph with $n$ vertices admitting a $k$-deque layout. Let also
$v_{1}\prec\dots\prec v_{n}$ be the linear order of the vertices of $G$. Since
each deque induces a planar graph, it has at most $3n-6$ edges. However, the
$n-1$ so-called _spine edges_ $(v_{i},v_{i+1})$, $i=1,\dots,n-1$ can be added
as head-head edges to every deque of the layout. So, every deque has at most
$2n-5$ non-spine edges. Hence, in total $G$ has $(2n-5)k+n-1$ edges. ∎

We are now ready to prove that the deque-number of the complete graph $K_{n}$
is $\lceil\frac{n}{4}\rceil$.

######  Theorem 3.

The deque-number of $K_{n}$ is $\lceil\frac{n}{4}\rceil$.

###### Proof.

The upper bound follows from 1 and [8]. For the lower bound, let $k$ be the
number of deques of $K_{n}$. Since $K_{n}$ has $\frac{n(n-1)}{2}$ edges, by
Lemma 2, it follows that $(2k+1)n-5k-1\geq\frac{n^{2}-n}{2}$, which implies:

$k\geq\frac{n^{2}-3n+2}{4n-10}\quad\text{for $n$ $\geq 3$}$

To complete the proof of the theorem, we next show that
$\lceil\frac{n^{2}-3n+2}{4n-10}\rceil=\lceil\frac{n}{4}\rceil$. We do this in
two steps. We first prove that
$\lceil\frac{n^{2}-3n+2}{4n-10}\rceil-\lceil\frac{n}{4}\rceil\leq 0$.

$\left\lceil\frac{n^{2}-3n+2}{4n-10}\right\rceil-\left\lceil\frac{n}{4}\right\rceil\leq\left\lceil\frac{n}{4}\cdot\frac{n-3}{n-\frac{10}{4}}\right\rceil-\left\lceil\frac{n}{4}\right\rceil\leq
0$

We next prove that
$\lceil\frac{n^{2}-3n+2}{4n-10}\rceil-\lceil\frac{n}{4}\rceil\geq 0$ holds.

$\left\lceil\frac{n^{2}-3n+2}{4n-10}\right\rceil-\left\lceil\frac{n}{4}\right\rceil\geq\left\lceil\frac{n}{4}\cdot\frac{n+\frac{2}{n}}{n-\frac{5}{2}}\right\rceil-\left\lceil\frac{n}{4}\right\rceil\geq
0$

Hence, the proof is completed. ∎

For rique layouts, the analog of Lemma 2 is the following, which has been used
to show a lower bound of $(1-\frac{\sqrt{2}}{2})(n-2)$ on the rique-number of
$K_{n}$ [4].

######  Lemma 4 (Bekos et al. [4]).

A graph with $n$ vertices admitting a rique layout with $k$ pages has at most
$(2n+2)k-k^{2}+(n-3)$ edges.

In the next theorem, we improve the best-known upper bound on the rique-number
of $K_{n}$ from $\lceil\frac{n}{3}\rceil$ [4] to
$\lfloor\frac{n-1}{3}\rfloor$.

######  Theorem 5.

The rique-number of $K_{n}$ is at most $\lfloor\frac{n-1}{3}\rfloor$.

###### Proof.

For our proof, we distinguish three cases, namely, $n\bmod 3\in\\{0,1,2\\}$.
We describe each of these cases separately in the following.

Case 1: $n\bmod 3=0$. We start our proof assuming $n\bmod 3=0$ and we prove
that $K_{n}$ admits a rique layout $\mathcal{L}$ with $\frac{n}{3}-1$ riques.
Our construction contains seven “special” pages, namely, the ones in
$\\{1,2,3,4,\frac{n}{3}-3,\frac{n}{3}-2,\frac{n}{3}-1$}; blue, red, green,
dark-purple, gray, light-purple and yellow in Fig. 9(a). The remaining pages
of $\mathcal{L}$ are uniform.

Page 1 of $\mathcal{L}$ contains the following $2n$ edges; see Fig. 2:

  * -

$\\{(v_{1},v_{j}),j=2,\dots,n\\}_{ht}$; dark red in Fig. 2,

  * -

$\\{(v_{i},v_{n}),i=2,\dots,\frac{n}{3}\\}_{ht}$; red in Fig. 2,

  * -

$\\{(v_{\frac{n}{3}},v_{j}),j=\frac{n}{3}+1,\dots,\frac{2n}{3}+1\\}_{hh}$;
light red in Fig. 2,

  * -

$\\{(v_{\frac{2n}{3}+1},v_{j}),j=\frac{2n}{3}+2,\dots,n\\}_{hh}$; blue in Fig.
2,

  * -

$\\{(v_{n-1},v_{n})\\}_{hh}$; light blue in Fig. 2 .

Figure 2: Page $1$ of $\mathcal{L}$ when $n\bmod 3=0$.

Page 2 of $\mathcal{L}$ contains the following $2n-7$ edges:

  * -

$\\{(v_{2},v_{j}),j=3,\dots,n-1\\}_{ht}$; dark red in Fig. 3,

  * -

$\\{(v_{i},v_{n-1}),i=3,\dots,\frac{n}{3}+1\\}_{ht}$; red in Fig. 3,

  * -

$\\{(v_{\frac{n}{3}+1},v_{n})\\}_{ht}$; orange in Fig. 3,

  * -

$\\{(v_{\frac{n}{3}+1},v_{j}),j=\frac{n}{3}+2,\dots,\frac{2n}{3}\\}_{hh}$;
blue in Fig. 3,

  * -

$\\{(v_{\frac{2n}{3}},v_{j}),j=\frac{2n}{3}+1,\dots,n\\}_{hh}$; light blue in
Fig. 3.

Figure 3: Page $2$ of $\mathcal{L}$ when $n\bmod 3=0$.

Page 3 of $\mathcal{L}$ contains the following $2n-5$ edges:

  * -

$\\{(v_{3},v_{j}),j=4,\dots,n-2\\}_{ht}$; dark red in Fig. 4,

  * -

$\\{(v_{i},v_{n-2}),i=4,\dots,\frac{n}{3}+1\\}_{ht}$; red in Fig. 4,

  * -

$\\{(v_{\frac{2n}{3}+2},v_{j}),j=n-2,\dots,n\\}_{ht}$; orange in Fig. 4,

  * -

$\\{(v_{\frac{n}{3}+1},v_{\frac{2n}{3}+1})\\}_{hh}$; blue in Fig. 4,

  * -

$\\{(v_{\frac{n}{3}+2},v_{j}),j=\frac{2n}{3}-1,\frac{2n}{3},\frac{2n}{3}+1\\}_{hh}$;
light blue in Fig. 4,

  * -

$\\{(v_{\frac{n}{3}+3},v_{j}),j=\frac{n}{3}+4,\dots,\frac{2n}{3}-1\\}_{hh}$;
pink in Fig. 4,

  * -

$\\{(v_{\frac{2n}{3}+2},v_{j}),j=\frac{2n}{3}+3,\dots,n-3\\}_{hh}$; light red
in Fig. 4,

  * -

$\\{(v_{n-3},v_{j}),j=n-2,n-1,n\\}_{hh}$; light orange in Fig. 4.

Figure 4: Page $3$ of $\mathcal{L}$ when $n\bmod 3=0$.

For $p=4,\dots,\frac{n}{3}-4$, page $p$ of $\mathcal{L}$ contains the
following $\frac{n}{3}-2p+3$ edges:

  * -

$\\{(v_{p},v_{j}),j=p+1,\dots,n-p+1\\}_{ht}$; dark red in Fig. 5,

  * -

$\\{(v_{i},v_{j}),i=p+1,\dots\frac{n}{3}+1,j=n-p+1\\}_{ht}$; red in Fig. 5,

  * -

$\\{(v_{i},v_{j}),i=\frac{n}{3}+(p+1),j=n-p+1,\dots,n\\}_{ht}$; pink in Fig.
5,

  * -

$\\{(v_{i},v_{j}),i=\frac{n}{3}+(p+1),j=\frac{2n}{3}+(p-2),\dots,n-p\\}_{hh}$;
blue in Fig. 5,

  * -

$\\{(v_{i},v_{j}),i=n-p+1,j=n-p,\dots,n\\}_{hh}$; light blue in Fig. 5,

  * -

$\\{(v_{i},v_{j}),i=\frac{n}{3}+(p+2),j=\frac{n}{3}+(p+3),\dots,\frac{2n}{3}+(p-2)\\}_{hh}$;
orange in Fig. 5.

Figure 5: Page $p=4,\dots,\frac{n}{3}-4$ of $\mathcal{L}$ when $n\bmod 3=0$.

Page $\frac{n}{3}-3$ of $\mathcal{L}$ contains the following $\frac{4n}{3}+6$
edges:

  * -

$\\{(v_{\frac{n}{3}-3},v_{j}),j=\frac{n}{3}-2,\dots,\frac{2n}{3}+4\\}_{ht}$;
dark red in Fig. 6,

  * -

$\\{(v_{i},v_{\frac{2n}{3}+4}),i=\frac{n}{3}-2,\dots,\frac{n}{3}+1\\}_{ht}$;
red in Fig. 6,

  * -

$\\{(v_{\frac{n}{3}+3},v_{j}),j=\frac{2n}{3}+4,\dots,n-1\\}_{ht}$; light blue
in Fig. 6,

  * -

$\\{(v_{\frac{2n}{3}+3},v_{j}),j=n-1,n\\}_{ht}$; pink in Fig. 6,

  * -

$\\{(v_{\frac{n}{3}+3},v_{j}),j=\frac{2n}{3},\dots,\frac{2n}{3}+3\\}_{hh}$;
dark blue in Fig. 6,

  * -

$\\{(v_{\frac{n}{3}+4},v_{j}),j=\frac{n}{3}+5,\dots,\frac{2n}{3}\\}_{hh}$;
orange in Fig. 6,

  * -

$\\{(v_{\frac{2n}{3}+3},v_{j}),j=\frac{2n}{3}+3,\dots,n-2\\}_{hh}$; red in
Fig. 6,

  * -

$\\{(v_{n-2},v_{j}),j=n-1,n\\}_{hh}$; dark orange in Fig. 6.

Figure 6: Page $\frac{n}{3}-3$ of $\mathcal{L}$ when $n\bmod 3=0$.

Page $\frac{n}{3}-2$ of $\mathcal{L}$ contains the following $\frac{4n}{3}+3$
edges:

  * -

$\\{(v_{\frac{n}{3}-2},v_{j}),j=\frac{n}{3}-1,\dots,\frac{2n}{3}+3\\}_{ht}$;
dark red in Fig. 7,

  * -

$\\{(v_{i},v_{\frac{2n}{3}+3}),i=\frac{n}{3}-1,\dots,\frac{n}{3}+1\\}_{ht}$;
red in Fig. 7,

  * -

$\\{(v_{\frac{n}{3}+2},v_{j}),j=\frac{2n}{3}+3,\dots,n\\}_{ht}$; light red in
Fig. 7,

  * -

$\\{(v_{\frac{n}{3}+3},v_{n})_{ht}$; pink in Fig. 7,

  * -

$\\{(v_{\frac{n}{3}+4},v_{j}),j=\frac{2n}{3}+1,\dots,n\\}_{hh}$; dark orange
in Fig. 7,

  * -

$\\{(v_{\frac{n}{3}+5},v_{j}),j=\frac{n}{3}+6,\dots,\frac{2n}{3}+1\\}_{hh}$;
orange in Fig. 7.

Figure 7: Page $\frac{n}{3}-2$ of $\mathcal{L}$ when $n\bmod 3=0$.

Page $\frac{n}{3}-1$ of $\mathcal{L}$ contains the following $n+9$ edges:

  * -

$\\{(v_{\frac{n}{3}-1},v_{j}),j=\frac{n}{3},\dots,\frac{2n}{3}+2\\}_{ht}$;
dark red in Fig. 8,

  * -

$\\{(v_{i},v_{\frac{2n}{3}+2}),i=\frac{n}{3},\dots,\frac{n}{3}+2\\}_{ht}$;red
in Fig. 8,

  * -

$\\{(v_{\frac{2n}{3}-2},v_{j}),j=n-5,\dots,n\\}_{ht}$; light red in Fig. 8,

  * -

$\\{(v_{\frac{n}{3}+2},v_{j}),j=\frac{n}{3}+3,\dots,\frac{2n}{3}-2\\}_{hh}$;
orange in Fig. 8,

  * -

$\\{(v_{\frac{2n}{3}-1},v_{j}),j=\frac{2n}{3},\dots,n\\}_{hh}$; light orange
in Fig. 8.

Figure 8: Page $\frac{n}{3}-1$ of $\mathcal{L}$ when $n\bmod 3=0$.

(a)

(b)

(c)

Figure 9: Illustration of the grid representation of a rique layout of $K_{n}$
with (a) $n\bmod 3=0$ (b) $n\bmod 3=1$, and (c) $n\bmod 3=2$, in which paths
of the same color correspond to the same rique. The points of the grid that
are covered by a solid (dashed) path are head-head (head-tail, respectively).

So, in total $\mathcal{L}$ has
$(2n-1)+(2n-6)+(2n-4)+(\frac{5n}{3}-5)+\sum_{p=5}^{\frac{n}{3}-4}(\frac{5n}{3}-p+1)+(n+14)+(\frac{4n}{3}+3)+(\frac{4n}{3}+3)=\frac{n(n-1)}{2}$
edges. Since no two edges have been assigned to the same rique and all edges
in the same rique form a cylindric layout, it follows that the rique number of
$K_{n}$ is at most $\lfloor\frac{n-1}{3}\rfloor$ when $n\bmod 3=0$.

Case 2: $n\bmod 3=1$. In this case, we show that the $K_{n}$ admits a rique
layout with $\lfloor\frac{n}{3}\rfloor$ riques. As in Case 1, our construction
contains again “special” pages, namely, the ones in
$\\{1,2,\lfloor\frac{n-1}{3}\rfloor$}; blue, red and purple in Fig. 9(b). The
remaining pages of $\mathcal{L}$ are uniform.

Page $1$ of $\mathcal{L}$ contains the following $2n-1$ edges:

  * -

$\\{(u_{1},v_{j}),j=2,\dots,n\\}_{ht}$; dark red in Fig. 10,

  * -

$\\{(u_{i},v_{n}),i=2,\dots,\frac{n-1}{3}+1\\}_{ht}$; red in Fig. 10,

  * -

$\\{(u_{\frac{n-1}{3}+1},v_{j}),j=\frac{n-1}{3}+2,\dots,\frac{2n-2}{3}+1\\}_{hh}$;
light red in Fig. 10,

  * -

$\\{(u_{\frac{2n-2}{3}+1},v_{j}),j=\frac{2n-2}{3}+2,\dots,n\\}_{hh}$; blue in
Fig. 10,

  * -

$\\{(u_{n-1},v_{n})\\}_{hh}$; light blue in Fig. 10.

Figure 10: Page $1$ of $\mathcal{L}$ when $n\bmod 3=1$. Figure 11: Page $2$ of
$\mathcal{L}$ when $n\bmod 3=1$.

Page $2$ of $\mathcal{L}$ contains the following $2n-4$ edges:

  * -

$\\{(u_{2},v_{j}),j=3,\dots,n-1\\}_{ht}$; dark red in Fig. 11,

  * -

$\\{(u_{i},v_{n-1}),i=3,\dots,\frac{n-1}{3}+1\\}_{ht}$; red in Fig. 11,

  * -

$\\{(u_{\frac{n-1}{3}+2},v_{j}),j=n-1,n\\}_{ht}$; light red in Fig. 11,

  * -

$\\{(u_{\frac{n-1}{3}+2},v_{j}),j=\frac{n-1}{3}+3\dots,n-2\\}_{hh}$; blue in
Fig. 11,

  * -

$\\{(u_{n-2},v_{j}),j=n-1,n\\}_{hh}$; light blue in Fig. 11.

For $p=3,\dots,\frac{n-1}{3}-1$, page $p$ of $\mathcal{L}$ contains the
following $2n-3p+2$ edges:

  * -

$\\{(u_{p},v_{j}),j=p+1,\dots,n-p+1\\}_{ht}$; dark red in Fig. 12,

  * -

$\\{(u_{i},v_{n-p+1}),i=p+1,\dots,\frac{n-1}{3}+1\\}_{ht}$; red in Fig. 12,

  * -

$\\{(u_{\frac{n-1}{3}+p},v_{j}),j=n-p+1,\dots,n\\}_{ht}$; orange in Fig. 12,

  * -

$\\{(u_{\frac{n-1}{3}+p},v_{j}),j=\frac{n-1}{3}+(p+1),\dots,n-p\\}_{hh}$; blue
in Fig. 12,

  * -

$\\{(u_{n-p},v_{j}),j=n-p+1,\dots,n\\}_{hh}$; light blue in Fig. 12.

Figure 12: Page $p=3,\dots,\frac{n-1}{3}-1$ of $\mathcal{L}$ when $n\bmod
3=1$.

Page $\lfloor\frac{n-1}{3}\rfloor$ of $\mathcal{L}$ contains the following
$2(\frac{n-1}{3})+4$ edges:

  * -

$\\{(u_{\frac{n-1}{3}},v_{j}),j=\frac{n-1}{3}+1,\dots,\frac{2n-2}{3}+2)\\}_{ht}$;
dark red in Fig. 13,

  * -

$\\{(u_{\frac{n-1}{3}+1},v_{\frac{2n-2}{3}+2}),\\}_{ht}$; red in Fig. 13,

  * -

$\\{(u_{\frac{2n-2}{3}},v_{j}),j=\frac{2n-2}{3}+1,\dots,n\\}_{hh}$; orange in
Fig. 13.

Figure 13: Page $\lfloor\frac{n-1}{3}\rfloor$ of $\mathcal{L}$ when $n\bmod
3=1$.

So, when $n\bmod 3=1$, $\mathcal{L}$ has
$2n-1+2n-4+\sum_{p=3}^{\frac{n-1}{3}-1}(2n-3p+2)+2(\frac{n-1}{3})+4=\frac{n(n-1)}{2}$
edges. Since no two edges have been assigned to the same rique and all edges
in the same rique form a cylindric layout, it follows that the rique number of
$K_{n}$ is at most $\lfloor\frac{n-1}{3}\rfloor$ when $n\bmod 3=1$.

Case 3: $n\bmod 3=2$. We continue with the case $n\bmod 3=2$. In this case, we
show that the $K_{n}$ admits a rique layout with $\lfloor\frac{n}{3}\rfloor$
riques. As with the previous two cases, our construction contains again
“special” pages, namely, the ones in $\\{1,2$}; blue and red in Fig. 9(c). The
remaining pages of $\mathcal{L}$ are uniform.

Page $1$ of $\mathcal{L}$ contains the following $2n$ edges:

  * -

$\\{(u_{1},v_{j}),j=2,\dots,n\\}_{ht}$; dark red in Fig. 14,

  * -

$\\{(u_{i},v_{n}),i=2,\dots,\frac{n-2}{3}+1\\}_{ht}$; red in Fig. 14,

  * -

$\\{(u_{\frac{n-2}{3}+1},v_{j}),j=\frac{n-2}{3}+2,\dots,\frac{2n-4}{3}+2\\}_{hh}$;
light red in Fig. 14,

  * -

$\\{(u_{\frac{2n-4}{3}+2},v_{j}),j=\frac{2n-4}{3}+3,\dots,n\\}_{hh}$; blue in
Fig. 14,

  * -

$\\{(u_{n-1},v_{n})\\}_{hh}$; light blue in Fig. 14.

Figure 14: Page $1$ of $\mathcal{L}$ when $n\bmod 3=2$. Figure 15: Page $2$ of
$\mathcal{L}$ when $n\bmod 3=2$.

Page $2$ of $\mathcal{L}$ contains the following $2n-4$ edges:

  * -

$\\{(u_{2},v_{j}),j=3,\dots,n-1\\}_{ht}$; dark red in Fig. 15,

  * -

$\\{(u_{i},v_{n-1}),i=3,\dots,\frac{n-2}{3}+2\\}_{ht}$; red in Fig. 15,

  * -

$\\{(u_{\frac{n-2}{3}+2},v_{j}),j=n-1,n\\}_{ht}$; light red in Fig. 15,

  * -

$\\{(u_{\frac{n-2}{3}+2},v_{j}),j=\frac{n-2}{3}+3\dots,n-2\\}_{hh}$; blue in
Fig. 15,

  * -

$\\{(u_{n-2},v_{j}),j=n-1,n\\}_{hh}$; light blue in Fig. 15.

For $p=3,\dots,\frac{n-2}{3}$, page $p$ of $\mathcal{L}$ contains the
following $2n-3p+2$ edges:

  * -

$\\{(u_{p},v_{j}),j=p+1,\dots,n-p+1\\}_{ht}$; dark red in Fig. 16,

  * -

$\\{(u_{i},v_{n-p+1}),i=p+1,\dots,\frac{n-2}{3}+1\\}_{ht}$; red in Fig. 16,

  * -

$\\{(u_{\frac{n-2}{3}+p},v_{j}),j=n-p+1,\dots,n\\}_{ht}$;light red in Fig. 16,

  * -

$\\{(u_{\frac{n-2}{3}+p},v_{j}),j=\frac{n-2}{3}+(p+1),\dots,n-p\\}_{hh}$; blue
in Fig. 16,

  * -

$\\{(u_{n-p},v_{j}),j=n-p+1,\dots,n\\}_{hh}$; light blue in Fig. 16.

Figure 16: Page $p=3,\dots,\frac{n-2}{3}$ of $\mathcal{L}$ when $n\bmod 3=2$.

So, in total $\mathcal{L}$ has
$2n+2n-4+\sum_{p=3}^{\frac{n-2}{3}}(2n-3p+2)=\frac{n(n-1)}{2}$ edges. Since no
two edges have been assigned to the same rique and all edges in the same rique
form a cylindric layout, it follows that the rique number of $K_{n}$ is at
most $\lfloor\frac{n-1}{3}\rfloor$ when $n\bmod 3=2$. ∎

######  Remark 1.

Using the SAT formulation that we present in Section 5 we were able to show
that the upper bound of Theorem 5 is tight for all values of $n\leq 30$.
However, we were not able to show a matching lower bound. In view of these
observations, we conjecture in Section 6 that the rique-number of $K_{n}$ is
exactly $\lfloor\frac{n-1}{3}\rfloor$.

##  4 Complete bipartite graphs

In this section, we study the deque- and rique-numbers of the complete
bipartite graph $K_{n,n}$. Let the two parts of $K_{n,n}$ be
$A=\\{a_{1},\dots,a_{n}\\}$ and $B=\\{b_{1},\dots,b_{n}\\}$ with $|A|=|B|=n$.
W.l.o.g., we may assume that in the computed layouts $a_{1}\prec\dots\prec
a_{n}$ and $b_{1}\prec\dots\prec b_{n}$ holds.

######  Theorem 6.

The deque-number of $K_{n,n}$ is at most $\lceil\frac{n}{3}\rceil$.

###### Proof.

Assume that $n\bmod 3=0$; the remaining cases follow from this one. We
describe a deque layout $\mathcal{L}$ of $K_{n,n}$ with $\frac{n}{3}$ deques,
in which the underlying order is: $a_{1}\prec\dots\prec a_{n/3}\prec
b_{1}\dots\prec b_{2n/3}\prec a_{n/3+1}\prec\dots\prec a_{n}\prec
b_{2n/3+1}\prec\dots\prec b_{n}$; for an illustration of the corresponding
matrix representation refer to Fig. 26 and observe that it consists of four
blocks, e.g., the middle block corresponds to the edges between
$a_{n/3+1},\dots,a_{n}$ and $b_{1},\dots,b_{2n/3}$.

Page 1 of $\mathcal{L}$ contains the following $2n+16$ edges:

  * -

$\\{(a_{1},b_{j}),j=\frac{2n}{3}+4,\dots,n\\}_{hh}$; dark red in Fig. 17,

  * -

$\\{(a_{1},b_{6})\\}_{hh}$; red in Fig. 17,

  * -

$\\{(a_{2},b_{j}),j=1,\dots,6\\}_{hh}$; light red in Fig. 17,

  * -

$\\{(a_{\frac{n}{3}+8},b_{j}),j=8,9,10\\}_{hh}$; orange in Fig. 17,

  * -

$\\{(a_{i},b_{10}),i=\frac{n}{3}+1,\dots,\frac{n}{3}+7\\}_{hh}$; light orange
in Fig. 17,

  * -

$\\{(a_{i},b_{\frac{2n}{3}+4}),i=\frac{n}{3}+8,\dots,n\\}_{hh}$; green in Fig.
17,

  * -

$\\{(a_{2},b_{j}),j=n-2,\dots,n\\}_{tt}$; dark blue in Fig. 17,

  * -

$\\{(a_{i},b_{\frac{2n}{3}+5}),i=\frac{n}{3}-2,\dots,\frac{n}{3}\\}_{tt}$;
blue in Fig. 17,

  * -

$\\{(a_{\frac{n}{3}},b_{j}),j=\frac{2n}{3}+1,\frac{2n}{3}+2)\\}_{tt}$; light
blue in Fig. 17.

  * -

$\\{(a_{n},b_{1}),(a_{n},b_{2}),(a_{n-1},b_{2})\\}_{tt}$; pink in Fig. 17,

  * -

$\\{(a_{i},b_{j}),(a_{i-1},b_{j}),i=n-1,\dots,\frac{2n}{3}+3,j=4,\dots,\frac{n}{3}\\}_{tt}$;
light pink in Fig. 17,

  * -

$\\{(a_{i},b_{\frac{n}{3}}),i=\frac{2n}{3}+1,\frac{2n}{3}+2\\}_{tt}$; dark
orange in Fig. 17,

  * -

$\\{(a_{\frac{2n}{3}+1},b_{j}),j=\frac{n}{3}+1,\dots,\frac{n}{3}+3\\}_{tt}$;
dark green in Fig. 17,

  * -

$\\{(a_{i},b_{\frac{n}{3}+3}),i=\frac{n}{3}+1,\dots,\frac{2n}{3}\\}_{tt}$;
green in Fig. 17.

Figure 17: Page $1$ of $\mathcal{L}$.

Page 2 of $\mathcal{L}$ contains the following $\frac{8n}{3}+5$ edges:

  * -

$\\{(a_{1},b_{\frac{2n}{3}+3})\\}_{ht}$; black in Fig. 18,

  * -

$\\{(a_{2},b_{j}),j=\frac{2n}{3}+3,\dots,n-3\\}_{ht}$; dark red in Fig. 18,

  * -

$\\{(a_{3},b_{j}),j=n-3,\dots,n-1\\}_{ht}$; red in Fig. 18,

  * -

$\\{(a_{i},b_{n}),i=3,\dots,\frac{n}{3}\\}_{ht}$; dark orange in Fig. 18,

  * -

$\\{(a_{i},b_{1}),i=n-3,n-4\\}_{hh}$; light orange in Fig. 18,

  * -

$\\{(a_{i},b_{2}),i=n-4,n-5\\}_{hh}$; dark orange in Fig. 18,

  * -

$\\{(a_{i},b_{j}),(a_{i-1},b_{j})i=n-5,\dots,\frac{2n}{3}+1,j=4,\dots,\frac{n}{3}-2\\}_{hh}$;
dark pink in Fig. 18,

  * -

$\\{(a_{i},b_{\frac{n}{3}-2}),i=\frac{2n}{3}+1,\dots,\frac{2n}{3}-1\\}_{hh}$;
light pink in Fig. 18,

  * -

$\\{(a_{\frac{2n}{3}-1},b_{j}),j=\frac{n}{3}-1,\frac{n}{3}\\}_{hh}$; light
gray in Fig. 18,

  * -

$\\{(a_{i},b_{\frac{n}{3}+1}),i=\frac{n}{3}+1,\dots,\frac{2n}{3}-1\\}_{hh}$;
gray in Fig. 18,

  * -

$\\{(a_{i},b_{n}),i=n-3,\dots,n\\}_{hh}$; pink in Fig. 18,

  * -

$\\{(a_{1},b_{i}),i=1,\dots,5\\}_{tt}$; light green in Fig. 18,

  * -

$\\{(a_{i},b_{j}),(a_{i},b_{j+1}),i=n-1,\dots,\frac{2n}{3}+4,j=5,\dots,\frac{n}{3}\\}_{tt}$;
green in Fig. 18,

  * -

$\\{(a_{i},b_{\frac{n}{3}+1}),i=\frac{2n}{3}+2,\frac{2n}{3}+3\\}_{tt}$; dark
blue in Fig. 18,

  * -

$\\{(a_{\frac{2n}{3}+2},b_{j}),i=\frac{n}{3}+2,\frac{n}{3}+3\\}_{tt}$; blue in
Fig. 18,

  * -

$\\{(a_{i},b_{\frac{n}{3}+4}),i=\frac{n}{3}+1,\dots,\frac{2n}{3}+2\\}_{tt}$;
light blue in Fig. 18.

Figure 18: Page $2$ of $\mathcal{L}$.

Page $p=3,4$ of $\mathcal{L}$ contains the following $\frac{8n}{3}+p+5$ edges:

  * -

$\\{(a_{i},b_{2p+1}),i=1,\dots,p-1\\}_{tt}$; green in Fig. 19,

  * -

$\\{(a_{p},b_{j}),j=1,\dots,2p+1\\}_{tt}$; dark green in Fig. 19,

  * -

$\\{(a_{i},b_{\frac{2n}{3}+5-p}),i=1,\dots,p-1)\\}_{ht}$; dark red in Fig. 19,

  * -

$\\{(a_{p},b_{j}),j=\frac{2n}{3}+5-p,\dots,n-1-p\\}_{ht}$; red in Fig. 19,

  * -

$\\{(a_{p+1},b_{j}),j=n-1-p,\dots,n+1-p\\}_{ht}$; pink in Fig. 19,

  * -

$\\{(a_{i},b_{n+2-p}),i=1+p,\dots,\frac{n}{3}\\}_{ht}$; light pink in Fig. 19,

  * -

$\\{(a_{i},b_{1}),i=n-2p+1,n-2p\\}_{hh}$; purple in Fig. 19,

  * -

$\\{(a_{i},b_{2}),i=n-2p,n-2p-1\\}_{hh}$; orange in Fig. 19,

  * -

$\\{(a_{i},b_{j}),(a_{i-1},b_{j})i=n-2p-1,\dots,\frac{2n}{3}+4-p,j=4,\dots,\frac{n}{3}-p-1\\}_{hh}$;
yellow in Fig. 19,

  * -

$\\{(a_{i},b_{\frac{n}{3}-p}),i=\frac{2n}{3}-p+3,\dots,\frac{2n}{3}-p+1\\}_{hh}$;
dark pink in Fig. 19,

  * -

$\\{(a_{\frac{2n}{3}-p},b_{j}),j=\frac{n}{3}-p+1,\frac{n}{3}-p+2\\}_{hh}$;
light yellow in Fig. 19,

  * -

$\\{(a_{i},b_{\frac{n}{3}-p+3}),i=\frac{n}{3}+1,\dots,\frac{2n}{3}-p+1\\}_{hh}$;
dark yellow in Fig. 19,

  * -

$\\{(a_{i},b_{j}),(a_{i},b_{j+1}),i=n-1,\dots,\frac{2n}{3}+p+2,j=5,\dots,\frac{n}{3}+p-2\\}_{tt}$,
light green in Fig. 19,

  * -

$\\{(a_{i},b_{\frac{n}{3}+p-1}),i=\frac{2n}{3}+p,\frac{2n}{3}+p+1\\}_{tt}$;blue
in Fig. 19,

  * -

$\\{(a_{\frac{2n}{3}+p},b_{j}),i=\frac{n}{3}+p,\frac{n}{3}+p+1\\}_{tt}$; dark
blue in Fig. 19,

  * -

$\\{(a_{i},b_{\frac{n}{3}+p+2}),i=\frac{n}{3}+1,\dots,\frac{2n}{3}+p\\}_{tt}$;
light blue in Fig. 19,

  * -

$\\{(a_{n+2-2p},b_{j}),j=n+2-p,\dots,n\\}_{hh}$; light gray in Fig. 19,

  * -

$\\{(a_{i},b_{n+2-p}),i=n+3-2p,\dots,n\\}_{hh}$; gray in Fig. 19,

  * -

$\\{(a_{n+1-2p},b_{j}),j=n+2-p,\dots,n\\}_{ht}$; black in Fig. 19.

Figure 19: Page $p=3,4$ of $\mathcal{L}$.

For $p=5,\dots,\frac{n}{3}-8$, page $p$ of $\mathcal{L}$ contains
$\frac{8n}{3}+2p+18$ edges:

  * -

$\\{(a_{i},b_{1}),i=n-2p+1,n-2p\\}_{hh}$; purple in Fig. 20,

  * -

$\\{(a_{i},b_{2}),i=n-2p,n-2p-1\\}_{hh}$; orange in Fig. 20,

  * -

$\\{(a_{i},b_{j}),(a_{i-1},b_{j})i=n-2p-1,\dots,\frac{2n}{3}+4-p,j=4,\dots,\frac{n}{3}-p-1\\}_{hh}$;
yellow in Fig. 20,

  * -

$\\{(a_{i},b_{\frac{n}{3}-p}),i=\frac{2n}{3}-p+3,\dots,\frac{2n}{3}-p+1\\}_{hh}$;
dark pink in Fig. 20,

  * -

$\\{(a_{\frac{2n}{3}-p},b_{j}),j=\frac{n}{3}-p+1,\frac{n}{3}-p+2\\}_{hh}$;
light yellow in Fig. 20,

  * -

$\\{(a_{i},b_{\frac{n}{3}-p+3}),i=\frac{n}{3}+1,\dots,\frac{2n}{3}-p+1\\}_{hh}$;
dark yellow in Fig. 20,

  * -

$\\{(a_{i},b_{j}),(a_{i},b_{j+1}),i=n-1,\dots,\frac{2n}{3}+p+2,j=5,\dots,\frac{n}{3}+p-2\\}_{tt}$;
light green in Fig. 20,

  * -

$\\{(a_{i},b_{\frac{n}{3}+p+2}),i=\frac{n}{3}+1,\dots,\frac{2n}{3}+p\\}_{tt}$;
light blue in Fig. 20,

  * -

$\\{(a_{\frac{2n}{3}+p},b_{j}),j=\frac{n}{3}+p-1,\dots,\frac{n}{3}+p+1\\}_{tt}$;
blue in Fig. 20,

  * -

$\\{(a_{\frac{2n}{3}+p+1},b_{\frac{n}{3}+p-1})\\}_{tt}$; dark blue in Fig. 20,

  * -

$\\{(a_{p},b_{j}),i=1,\dots,2p-1\\}_{tt}$; dark green in Fig. 20,

  * -

$\\{(a_{p+1},b_{j}),j=1,\dots,p-1\\}_{tt}$; green in Fig. 20,

  * -

$\\{(a_{i},b_{2p}),i=1,\dots,p\\}_{ht}$; dark red in Fig. 20,

  * -

$\\{(a_{p},b_{j}),j=\frac{2n}{3}+1,\dots,n-1-p\\}_{ht}$; red in Fig. 20,

  * -

$\\{(a_{p+1},b_{j}),j=n-1-p,\dots,n+1-p\\}_{ht}$; pink in Fig. 20,

  * -

$\\{(a_{i},b_{n+2-p}),i=p+1,\dots,\frac{n}{3}\\}_{ht}$; light pink in Fig. 20,

  * -

$\\{(a_{n+2-2p},b_{j}),j=n+2-p,\dots,n\\}_{hh}$; light gray in Fig. 20,

  * -

$\\{(a_{i},b_{n+2-p}),i=n+3-2p,\dots,n\\}_{hh}$; gray in Fig. 20,

  * -

$\\{(a_{n+1-2p},b_{j}),j=n+2-p,\dots,n\\}_{ht}$; black in Fig. 20.

Figure 20: Page $p=5,\dots,\frac{n}{3}-8$ of $\mathcal{L}$.

For $p=\frac{n}{3}-7,\dots,\frac{n}{3}-4$, page $p$ of $\mathcal{L}$ contains
$\frac{8n}{3}-2p-1$ edges:

  * -

$\\{(a_{i},b_{1}),i=n-2p+1,n-2p\\}_{hh}$; purple in Fig. 21,

  * -

$\\{(a_{i},b_{2}),i=n-2p,n-2p-1\\}_{hh}$; dark orange in Fig. 21,

  * -

$\\{(a_{i},b_{j}),(a_{i-1},b_{j}),i=n-2p-1,\dots,n-2p+3,j=4,\dots,6\\}_{hh}$;
yellow in Fig. 21,

  * -

$\\{(a_{i},b_{\frac{n}{3}-p}),i=\frac{2n}{3}-p+1,\dots,\frac{2n}{3}-p+3\\}_{hh}$
; dark pink in Fig. 21,

  * -

$\\{(a_{\frac{2n}{3}-p},b_{j}),j=\frac{n}{3}-p,\frac{n}{3}-p+1\\}_{hh}$; light
orange in Fig. 21,

  * -

$\\{(a_{i},b_{\frac{n}{3}-p+2}),i=\frac{n}{3}+1,\dots,\frac{2n}{3}-p\\}_{hh}$;
orange in Fig. 21,

  * -

$\\{(a_{i},b_{j}),(a_{i},b_{j+1}),i=n-1,\dots,n-5,j=2p,\dots,\frac{n}{3}+p-2\\}_{tt}$;
light green in Fig. 21,

  * -

$\\{(a_{i},b_{\frac{n}{3}+p+2}),i=\frac{n}{3}+1,\dots,\frac{2n}{3}+p\\}_{tt}$;
light blue in Fig. 21,

  * -

$\\{(a_{\frac{2n}{3}+p},b_{j}),j=\frac{n}{3}+p-1,\dots,\frac{n}{3}+p+1\\}_{tt}$;
blue in Fig. 21,

  * -

$\\{(a_{\frac{2n}{3}+p+1},b_{\frac{n}{3}+p-1})\\}_{tt}$; dark blue in Fig. 21,

  * -

$\\{(a_{p},b_{j}),i=1,\dots,2p-1\\}_{tt}$; dark green in Fig. 21,

  * -

$\\{(a_{p+1},b_{j}),j=1,\dots,p-1\\}_{tt}$; green in Fig. 21,

  * -

$\\{(a_{i},b_{2p}),i=1,\dots,p\\}_{ht}$; dark red in Fig. 21,

  * -

$\\{(a_{p},b_{j}),j=\frac{2n}{3}+1,\dots,n-1-p\\}_{ht}$; red in Fig. 21,

  * -

$\\{(a_{p+1},b_{j}),j=n-1-p,\dots,n+1-p\\}_{ht}$; pink in Fig. 21,

  * -

$\\{(a_{i},b_{n+2-p}),i=p+1,\dots,\frac{n}{3}\\}_{ht}$; light pink in Fig. 21,

  * -

$\\{(a_{n+2-2p},b_{j}),j=n+2-p,\dots,n\\}_{hh}$; light gray in Fig. 21,

  * -

$\\{(a_{i},b_{n+2-p}),i=n+3-2p,\dots,n\\}_{hh}$; gray in Fig. 21,

  * -

$\\{(a_{n+1-2p},b_{j}),j=n+2-p,\dots,n\\}_{ht}$; black in Fig. 21.

Figure 21: Page $p=\frac{n}{3}-7,\dots,\frac{n}{3}-4$ of $\mathcal{L}$.

Page $\frac{n}{3}-3$ of $\mathcal{L}$ contains the following
$\frac{10n}{3}+11$ edges:

  * -

$\\{(a_{i},b_{\frac{2n}{3}-6}),i=1,\dots,\frac{n}{3}-3\\}_{ht}$; dark red in
Fig. 22,

  * -

$\\{(a_{\frac{n}{3}-3},b_{j}),j=\frac{2n}{3}+1,\frac{2n}{3}+2\\}_{ht}$; red in
Fig. 22,

  * -

$\\{(a_{\frac{n}{3}-2},b_{j}),j=\frac{2n}{3}+2,\dots,\frac{2n}{3}+4\\}_{ht}$;
light red in Fig. 22,

  * -

$\\{(a_{i},b_{\frac{2n}{3}+4}),i=\frac{n}{3}-1,\frac{n}{3}\\}_{ht}$; orange in
Fig. 22,

  * -

$\\{(a_{i},b_{1}),i=\frac{n}{3}+6,\frac{n}{3}+7\\}_{hh}$; dark orange in Fig.
22,

  * -

$\\{(a_{i},b_{2}),i=\frac{n}{3}+3,\dots,\frac{n}{3}+6\\}_{hh}$; light orange
in Fig. 22,

  * -

$\\{(a_{\frac{n}{3}+3},b_{4})\\}_{hh}$; dark green in Fig. 22,

  * -

$\\{(a_{i},b_{5}),i=\frac{n}{3}+1,\dots,\frac{n}{3}+3\\}_{hh}$; pink in Fig.
22,

  * -

$\\{(a_{\frac{n}{3}+7},b_{j},j=\frac{2n}{3}+4,\dots,n\\}_{ht}$; yellow in Fig.
22,

  * -

$\\{(a_{\frac{n}{3}+8},b_{j}),j=\frac{2n}{3}+5,\dots,n\\}_{hh}$; dark blue in
Fig. 22,

  * -

$\\{(a_{i},b_{\frac{2n}{3}+6}),i=\frac{n}{3}+8,\dots,n\\}_{hh}$; blue in Fig.
22,

  * -

$\\{(a_{i},b_{\frac{2n}{3}-7}),i=1,\dots,\frac{n}{3}\\}_{tt}$; green in Fig.
22,

  * -

$\\{(a_{\frac{n}{3}},b_{j}),j=1,\dots,\frac{2n}{3}-6\\}_{tt}$; dark pink in
Fig. 22,

  * -

$\\{(a_{n-1},b_{j}),j=\frac{2n}{3}-5,\frac{2n}{3}-4\\}_{tt}$; black in Fig.
22,

  * -

$\\{(a_{i},b_{\frac{2n}{3}-4}),i=n-2,n-3\\}_{tt}$; gray in Fig. 22,

  * -

$\\{(a_{n-3},b_{j}),j=\frac{2n}{3}-3,\frac{2n}{3}-2\\}_{tt}$; light blue in
Fig. 22,

  * -

$\\{(a_{i},b_{\frac{2n}{3}-1}),i=\frac{n}{3}+1,\dots,n-3\\}_{tt}$; dark gray
in Fig. 22.

Figure 22: Page $\frac{n}{3}-3$ of $\mathcal{L}$.

Page $\frac{n}{3}-2$ of $\mathcal{L}$ contains the following
$\frac{10n}{3}+13$ edges:

  * -

$\\{(a_{i},b_{\frac{2n}{3}-4}),i=1,\dots,\frac{n}{3}-2\\}_{ht}$; dark red in
Fig. 23,

  * -

$\\{(a_{\frac{n}{3}-2},b_{\frac{2n}{3}+1})\\}_{ht}$; red in Fig. 23,

  * -

$\\{(a_{\frac{n}{3}-1},b_{j}),j=\frac{2n}{3}+1,\dots,\frac{2n}{3}+3\\}_{ht}$;
light red in Fig. 23,

  * -

$\\{(a_{\frac{n}{3}},b_{\frac{2n}{3}+3}\\}_{ht}$; dark gray in Fig. 23,

  * -

$\\{(a_{i},b_{1}),i=\frac{n}{3}+2,\dots,\frac{n}{3}+5\\}_{hh}$; light pink in
Fig. 23,

  * -

$\\{(a_{\frac{n}{3}+2},b_{2}),(a_{\frac{n}{3}+2},b_{4}),(a_{\frac{n}{3}+1},b_{4})\\}_{hh}$;
gold in Fig. 23,

  * -

$\\{(a_{\frac{n}{3}+5},b_{j}),j=\frac{2n}{3}+3,\dots,n\\}_{ht}$; gray in Fig.
23

  * -

$\\{(a_{\frac{n}{3}+6},b_{j}),j=\frac{2n}{3}+3,\dots,n\\}_{hh}$; light blue in
Fig. 23,

  * -

$\\{(a_{i},b_{\frac{2n}{3}+3}),i=\frac{2n}{3}+6,\dots,n\\}_{hh}$; blue in Fig.
23,

  * -

$\\{(a_{i},b_{\frac{2n}{3}-5}),i=1,\dots,\frac{n}{3}-2\\}_{tt}$; orange in
Fig. 23,

  * -

$\\{(a_{\frac{n}{3}-2},b_{j}),j=1,\dots,\frac{2n}{3}-4\\}_{tt}$; dark pink in
Fig. 23,

  * -

$\\{(a_{n-1},b_{\frac{2n}{3}-3})\\}_{tt}$; black in Fig. 23,

  * -

$\\{(a_{n-2},b_{j}),j=\frac{2n}{3}-3,\dots,\frac{2n}{3}\\}_{tt}$; pink in Fig.
23,

  * -

$\\{(a_{i},b_{\frac{2n}{3}}),i=\frac{n}{3}+1,\dots,n-3\\}_{tt}$; dark blue in
Fig. 23.

Figure 23: Page $\frac{n}{3}-2$ of $\mathcal{L}$.

Page $\frac{n}{3}-1$ of $\mathcal{L}$ contains the following $\frac{11n}{3}-8$
edges:

  * -

$\\{(a_{i},b_{\frac{2n}{3}-3}),i=1,\dots,\frac{n}{3}-1\\}_{hh}$; dark red in
Fig. 24,

  * -

$\\{(a_{\frac{n}{3}-1},b_{j}),j=1,\dots,\frac{2n}{3}-4\\}_{hh}$; light red in
Fig. 24,

  * -

$\\{(a_{i},b_{\frac{2n}{3}-2}),i=1,\dots,\frac{n}{3}-1\\}_{th}$; red in Fig.
24,

  * -

$\\{(a_{n-1},b_{j}),j=\frac{2n}{3}-2,\dots,\frac{2n}{3}\\}_{ht}$; light orange
in Fig. 24,

  * -

$\\{(a_{\frac{n}{3}+2},b_{\frac{2n}{3}+1})\\}_{ht}$; dark blue in Fig. 24,

  * -

$\\{(a_{\frac{n}{3}+3},b_{j}),j=\frac{2n}{3}+1,\dots,n\\}_{ht}$; gray in Fig.
24,

  * -

$\\{(a_{\frac{n}{3}+4},b_{j}),j=\frac{2n}{3}+3,\dots,n\\}_{hh}$; light blue in
Fig. 24,

  * -

$\\{(a_{\frac{n}{3}+5},b_{\frac{2n}{3}+2}),(a_{\frac{n}{3}+5},b_{\frac{2n}{3}+3})\\}_{hh}$;
green in Fig. 24,

  * -

$\\{(a_{i},b_{\frac{2n}{3}+2}),i=\frac{n}{3}+6,\dots,n\\}_{hh}$; blue in Fig.
24,

  * -

$\\{(a_{n-1},b_{1}),(a_{n-2},b_{1}),(a_{n-2},b_{2}),(a_{n-3},b_{2})\\}_{tt}$;
orange in Fig. 24,

  * -

$\\{(a_{i},b_{j}),(a_{i-1},b_{j}),i=n-3,\dots,\frac{2n}{3}+2,j=4,\dots,\frac{n}{3}-2\\}_{tt}$;
yellow in Fig. 24,

  * -

$\\{(a_{i},b_{\frac{n}{3}-1},i=\frac{2n}{3}+2,\dots,\frac{2n}{3}\\}_{tt}$;
pink in Fig. 24,

  * -

$\\{(a_{\frac{2n}{3}},b_{j}),j=\frac{n}{3},\frac{n}{3}+1\\}_{tt}$; black in
Fig. 24,

  * -

$\\{(a_{i},b_{\frac{n}{3}+2}),i=\frac{n}{3}+1,\dots,\frac{2n}{3}\\}_{tt}$;
dark pink in Fig. 24,

Figure 24: Page $\frac{n}{3}-1$ of $\mathcal{L}$.

Page $\frac{n}{3}$ of $\mathcal{L}$ contains the following $4n+14$ edges:

  * -

$\\{(a_{i},b_{\frac{2n}{3}}),i=1,\dots,\frac{n}{3}\\}_{ht}$; dark red in Fig.
25,

  * -

$\\{(a_{\frac{n}{3}+1},b_{j}),j=1,2,3\\}_{ht}$; red in Fig. 25,

  * -

$\\{(a_{i},b_{3}),i=\frac{n}{3}+1,\dots,n\\}_{ht}$; dark orange in Fig. 25,

  * -

$\\{(a_{n},b_{j}),j=4,\dots,\frac{2n}{3}\\}_{ht}$; orange in Fig. 25,

  * -

$\\{(a_{\frac{n}{3}+2},b_{j}),j=\frac{2n}{3}+2,\dots,n\\}_{hh}$; gray in Fig.
25,

  * -

$\\{(a_{\frac{n}{3}+4},b_{\frac{2n}{3}+2})\\}_{hh}$; yellow in Fig. 25,

  * -

$\\{(a_{i},b_{\frac{2n}{3}+1}),i=\frac{n}{3}+4,\dots,n\\}_{hh}$; light blue in
Fig. 25,

  * -

$\\{(a_{\frac{n}{3}+1},b_{j}),j=\frac{2n}{3}+1,\dots,n\\}_{ht}$; light orange
in Fig. 25,

  * -

$\\{(a_{i},b_{\frac{2n}{3}-1}),i=1,\dots,\frac{n}{3}\\}_{ht}$; dark blue in
Fig. 25,

  * -

$\\{(a_{\frac{n}{3}},b_{j}),j=1,\dots,\frac{2n}{3}-1\\}_{ht}$; blue in Fig.
25.

Figure 25: Page $\frac{n}{3}$ of $\mathcal{L}$.

So, in total $\mathcal{L}$ has
$2n+16+\frac{8n}{3}+5+\sum_{p=3}^{4}(\frac{8n}{3}+p+5)+\sum_{p=\frac{n}{3}-7}^{\frac{n}{3}-4}(\frac{8n}{3}-2p-1)+\sum_{p=5}^{\frac{n}{3}-8}(\frac{8n}{3}+2p+18)+\frac{10n}{3}+11+\frac{10n}{3}+13+\frac{11n}{3}-8+4n+14=n^{2}$
edges. Since no two edges have been assigned to the same deque and all edges
in the same deque form a cylindric layout, it follows that the deque number of
$K_{n,n}$ is at most $\frac{n}{3}$. ∎

Figure 26: Illustration of the grid representation of a deque layout of
$K_{n,n}$, in which paths of the same color correspond to the same deque. The
points of the grid that are represented by a triangle pointing up (down)
correspond to head-$\star$ (tail-$\star$, resp.) edges; grid points covered by
a solid line are head-head or tail-tail edges; the dashed covered ones are
head-tail or tail-head

We complete this section by providing our upper bound on the rique-number of
$K_{n,n}$.

######  Theorem 7.

The rique-number of the complete bipartite graph $K_{n,n}$ is at most
$\lfloor\frac{n-1}{2}\rfloor-1$.

###### Proof.

For the proof, we distinguish two cases depending on whether $n$ is odd or
even.

Case 1: $n$ is odd. We first assume that $n$ is odd and we prove that
$K_{n,n}$ admits a rique layout $\mathcal{L}$ with
$\lfloor\frac{n}{2}\rfloor-1$ riques. Let $A=\\{a_{1},\dots,a_{n}\\}$ and
$B=\\{b_{1},\dots,b_{n}\\}$ be the two parts of $K_{n,n}$, such that
$a_{1}\prec b_{1}\prec a_{2}\prec b_{2}\prec\dots\prec
a_{\lfloor\frac{n}{2}\rfloor}\prec b_{\lfloor\frac{n}{2}\rfloor}\prec
b_{\lceil\frac{n}{2}\rceil}\prec\dots\prec b_{n}\prec
a_{\lceil\frac{n}{2}\rceil}\prec\dots\prec a_{n}$ holds in $\mathcal{L}$. In
$\mathcal{L}$, there exist 12 special riques, in particular, the ones in
$\\{1,2,3,4,5,6,7,\lfloor\frac{n}{2}\rfloor-5,\lfloor\frac{n}{2}\rfloor-4,\lfloor\frac{n}{2}\rfloor-3,\lfloor\frac{n}{2}\rfloor-2,\lfloor\frac{n}{2}\rfloor-1\\}$;
see Fig. 45.

Page 1 of $\mathcal{L}$ contains the following 3n edges:

  * -

$\\{(a_{1},b_{j}),j=1,\dots,n\\}_{ht}$; dark red in Fig. 27,

  * -

$\\{(a_{i},b_{1}),i=\lceil\frac{n}{2}\rceil,\dots,n\\}_{ht}$; red in Fig. 27,

  * -

$\\{(a_{\lfloor\frac{n}{2}\rfloor},b_{j}),j=2,\dots,\lfloor\frac{n}{2}\rfloor\\}_{hh}$;
gray in Fig. 27,

  * -

$\\{(a_{i},b_{2}),i=\lceil\frac{n}{2}\rceil,\dots,n\\}_{hh}$; blue in Fig. 27,

  * -

$\\{(a_{\lceil\frac{n}{2}\rceil},b_{j}),j=\lceil\frac{n}{2}\rceil,\dots,n\\}_{hh}$;
light blue in Fig. 27.

Figure 27: Page $1$ of $\mathcal{L}$ when $n$ is odd.

Page 2 of $\mathcal{L}$ contains the following $\frac{5n-1}{2}+1$ edges:

  * -

$\\{(a_{i},b_{1}),i=2,\dots,\lfloor\frac{n}{2}\rfloor\\}_{ht}$; dark red in
Fig. 28,

  * -

$\\{(a_{2},b_{\lfloor\frac{n}{2}\rfloor})\\}_{ht}$; yellow in Fig. 28,

  * -

$\\{(a_{2},b_{j}),j=\lceil\frac{n}{2}\rceil,\dots,n\\}_{ht}$; light red in
Fig. 28,

  * -

$\\{(a_{3},b_{n})\\}_{ht}$; red in Fig. 28,

  * -

$\\{(a_{i},b_{3}),i=\lceil\frac{n}{2}\rceil,\dots,n\\}_{ht}$; dark blue in
Fig. 28,

  * -

$\\{(a_{n-3},b_{j}),j=\lfloor\frac{n}{2}\rfloor-2,\dots,\lceil\frac{n}{2}\rceil+1\\}_{hh}$;
light blue in Fig. 28,

  * -

$\\{(a_{i},b_{\lceil\frac{n}{2}\rceil+1}),i=\lceil\frac{n}{2}\rceil+1,\dots,n-4\\}_{hh}$;
blue in Fig. 28,

  * -

$\\{(a_{\lceil\frac{n}{2}\rceil+1},b_{j}),j=\lceil\frac{n}{2}\rceil+2,\dots,n\\}_{hh}$;
gray in Fig. 28.

Figure 28: Page $2$ of $\mathcal{L}$ when $n$ is odd.

For $p=3,4,5$, page $p$ of $\mathcal{L}$ contains the following
$\left(\frac{5n-1}{2}\right)+1$ edges

  * -

$\\{(a_{p-1},b_{j}),j=2,\dots,\lfloor\frac{n}{2}\rfloor-p+2\\}_{ht}$; dark red
in Fig. 29,

  * -

$\\{(a_{p},b_{j}),j=\lfloor\frac{n}{2}\rfloor-p+2,\dots,n-p+2\\}_{ht}$; red in
Fig. 29,

  * -

$\\{(a_{p+1},b_{j}),j=n-p+2,\dots,n\\}_{ht}$; light red in Fig. 29,

  * -

$\\{(a_{i},b_{p+1}),i=\lceil\frac{n}{2}\rceil,\dots,n\\}_{ht}$; dark blue in
Fig. 29,

  * -

$\\{(a_{n+(p-5)},b_{j}),j=\lfloor\frac{n}{2}\rfloor-2,\dots,\lceil\frac{n}{2}\rceil+(p-1)\\}_{hh}$;
gray in Fig. 29,

  * -

$\\{(a_{i},b_{\lceil\frac{n}{2}\rceil+(p-1)}),i=\lceil\frac{n}{2}\rceil+(p-1),\dots,n+(p-6)\\}_{hh}$;
blue in Fig. 29,

  * -

$\\{(a_{\lceil\frac{n}{2}\rceil+(p-1)},b_{j}),j=\lceil\frac{n}{2}\rceil+p,\dots,n\\}_{hh}$;
light blue in Fig. 29.

Figure 29: Page $p=3,4,5$ of $\mathcal{L}$ when $n$ is odd.

Page 6 of $\mathcal{L}$ contains the following $\frac{5n-1}{2}-8$ edges:

  * -

$\\{(a_{5},b_{j}),j=2,\dots,\lfloor\frac{n}{2}\rfloor-4\\}_{ht}$; dark red in
Fig. 30,

  * -

$\\{(a_{6},b_{j}),j=\lfloor\frac{n}{2}\rfloor-4,\dots,n-4\\}_{ht}$; red in
Fig. 30,

  * -

$\\{(a_{7},b_{j}),j=n-4,\dots,n\\}_{ht}$; light red in Fig. 30,

  * -

$\\{(a_{i},b_{7}),i=\lceil\frac{n}{2}\rceil,\dots,n\\}_{ht}$; dark blue in
Fig. 30,

  * -

$\\{(a_{i},b_{\lceil\frac{n}{2}\rceil+5}),i=\lceil\frac{n}{2}\rceil+5,\dots,n)\\}_{hh}$;
blue in Fig. 30,

  * -

$\\{(a_{\lceil\frac{n}{2}\rceil+5},b_{j}),j=\lceil\frac{n}{2}\rceil+6,\dots,n\\}_{hh}$;
light red in Fig. 30.

Figure 30: Page $6$ of $\mathcal{L}$ when $n$ is odd. Figure 31: Page $7$ of
$\mathcal{L}$ when $n$ is odd.

Page 7 of $\mathcal{L}$ contains the following $\frac{3n+1}{2}+4$ edges:

  * -

$\\{(a_{6},b_{j}),j=2,\dots,\lfloor\frac{n}{2}\rfloor-5\\}_{ht}$; dark red in
Fig. 31,

  * -

$\\{(a_{7},b_{j}),j=\lfloor\frac{n}{2}\rfloor-5,\dots,n-5\\}_{ht}$; red in
Fig. 31,

  * -

$\\{(a_{8},b_{j}),j=n-5,\dots,n\\}_{ht}$; light red in Fig. 31,

  * -

$\\{(a_{i},b_{8}),i=\lceil\frac{n}{2}\rceil,\dots,n\\}_{ht}$; blue in Fig. 31,

  * -

$\\{(a_{\lfloor\frac{n}{2}\rfloor},b_{j}),j=\lceil\frac{n}{2}\rceil,\dots,\lceil\frac{n}{2}\rceil+2)\\}_{hh}$;
light blue in Fig. 31.

For $p=8,\dots,\frac{n-1}{2}-6$, page $p$ of $\mathcal{L}$ contains the
following $\frac{5n+3}{2}-2p+4$ edges:

  * -

$\\{(a_{p-1},b_{j}),j=2,\dots,\lfloor\frac{n}{2}\rfloor-p+2\\}_{ht}$; dark red
in Fig. 32,

  * -

$\\{(a_{p},b_{j}),j=\lfloor\frac{n}{2}\rfloor-p+2,\dots,n-p+2\\}_{ht}$; red in
Fig. 32,

  * -

$\\{(a_{p+1},b_{j}),j=n-p+2,\dots,n\\}_{ht}$; light red in Fig. 32,

  * -

$\\{(a_{i},b_{p+1}),i=\lceil\frac{n}{2}\rceil,\dots,n\\}_{ht}$; dark blue in
Fig. 32,

  * -

$\\{(a_{i},b_{\lceil\frac{n}{2}\rceil+p-2}),i=\lceil\frac{n}{2}\rceil+p-2,\dots,n)\\}_{hh}$;
blue in Fig. 32,

  * -

$\\{(a_{\lceil\frac{n}{2}\rceil+p-2},b_{j}),j=\lceil\frac{n}{2}\rceil+p-1,\dots,n\\}_{hh}$;
light blue in Fig. 32.

Figure 32: Page $p=8,\dots,\frac{n-1}{2}-6$ of $\mathcal{L}$ when $n$ is odd.

Page $\frac{n-1}{2}-5$ of $\mathcal{L}$ contains the following 2n-3 edges:

  * -

$\\{(a_{\lfloor\frac{n}{2}\rfloor-6},b_{j}),j=2,\dots,\lfloor\frac{n}{2}\rfloor-7\\}_{ht}$;
dark red in Fig. 33,

  * -

$\\{(a_{(\lfloor\frac{n}{2}\rfloor-5)},b_{j}),j=\lfloor\frac{n}{2}\rfloor-7,\dots,n-7\\}_{ht}$;
red in Fig. 33,

  * -

$\\{(a_{\lfloor\frac{n}{2}\rfloor-4},b_{j}),j=n-7,\dots,n\\}_{ht}$; light red
in Fig. 33,

  * -

$\\{(a_{i},b_{\lfloor\frac{n}{2}\rfloor-4}),i=\lceil\frac{n}{2}\rceil,\dots,n\\}_{ht}$;
light blue in Fig. 33,

  * -

$\\{(a_{i},b_{\lfloor\frac{n}{2}\rfloor-3}),i=\lceil\frac{n}{2}\rceil+5,\dots,n)\\}_{hh}$;
blue in Fig. 33.

Figure 33: Page $\frac{n-1}{2}-5$ of $\mathcal{L}$ when $n$ is odd.

For $p=\frac{n-1}{2}-k,$ with $k\in\\{4,3,2\\}$, page $p$ of $\mathcal{L}$
contains the following $\frac{3n-1}{2}-2k+20$ edges:

  * -

$\\{(a_{p-1},b_{j}),j=2,\dots,\lfloor\frac{n}{2}\rfloor-p-4\\}_{ht}$; dark red
in Fig. 34,

  * -

$\\{(a_{p},b_{j}),j=\lfloor\frac{n}{2}\rfloor-p-4,\dots,n-p-4\\}_{ht}$; red in
Fig. 34,

  * -

$\\{(a_{p+1},b_{j}),j=n-p-4,\dots,n\\}_{ht}$; light red in Fig. 34,

  * -

$\\{(a_{i},b_{p+1}),i=\lceil\frac{n}{2}\rceil,\dots,\lceil\frac{n}{2}\rceil+k\\}_{ht}$;
dark pink in Fig. 34,

  * -

$\\{(a_{i},b_{p+2}),i=\lceil\frac{n}{2}\rceil+k,\dots,n-8+k\\}_{ht}$; light
pink in Fig. 34,

  * -

$\\{(a_{n-8+k},b_{j}),j=\lfloor\frac{n}{2}\rfloor-2+k,\dots,\lceil\frac{n}{2}\rceil\\}_{ht}$;
pink in Fig. 34,

  * -

$\\{(a_{i},b_{n+(2k-9)}),i=n+(k-8),\dots,n\\}_{ht}$; dark blue in Fig. 34,

  * -

$\\{(a_{i},b_{n+(2k-8)}),i=n+(k-8),\dots,n)\\}_{hh}$; blue in Fig. 34,

  * -

$\\{(a_{n+(k-8)},b_{j}),j=n+(2k-7),\dots,n)\\}_{hh}$; gray in Fig. 34.

Figure 34: Page $p=\frac{n-1}{2}-k,$ with $k\in\\{4,3,2\\}$ of $\mathcal{L}$
when $n$ is odd.

Page $\frac{n-1}{2}-1$ of $\mathcal{L}$ contains the following
$\frac{3n+1}{2}+18$ edges:

  * -

$\\{(a_{\lfloor\frac{n}{2}\rfloor-1},b_{j}),j=2,\dots,\lceil\frac{n}{2}\rceil+3\\}_{ht}$;
dark red in Fig. 35,

  * -

$\\{(a_{\lfloor\frac{n}{2}\rfloor},b_{j}),j=\lceil\frac{n}{2}\rceil+3,\dots,n\\}_{ht}$;
red in Fig. 35,

  * -

$\\{(a_{i},b_{\lfloor\frac{n}{2}\rfloor}),i=\lceil\frac{n}{2}\rceil,\lceil\frac{n}{2}\rceil+1\\}_{ht}$;
light red in Fig. 35,

  * -

$\\{(a_{i},b_{\lceil\frac{n}{2}\rceil}),i=\lceil\frac{n}{2}\rceil+1,\dots,n-7\\}_{ht}$;
dark pink in Fig. 35,

  * -

$\\{(a_{i},b_{n-7}),i=\lceil\frac{n}{4}\rceil+1,\dots,n\\}_{ht}$; pink in Fig.
35,

  * -

$\\{(a_{i},b_{n-6}),i=\lfloor\frac{n}{4}\rfloor+1,\dots,n\\}_{hh}$; dark blue
in Fig. 35,

  * -

$\\{(a_{\lceil\frac{n}{4}\rceil+1},b_{j}),j=n-5,\dots,n\\}_{hh}$; blue in Fig.
35,

  * -

$\\{(a_{\lfloor\frac{n}{2}\rfloor-2},b_{j}),j=2,3\\}_{hh}$; gray in Fig. 35.

Figure 35: Page $\frac{n-1}{2}-1$ of $\mathcal{L}$ when $n$ is odd.

So, in total $\mathcal{L}$ has
$3n+\frac{5n-1}{2}+1+3\left(\frac{5n-1}{2}+1\right)+\frac{5n-1}{2}-8+\frac{3n+1}{2}+4+\sum_{p=8}^{\frac{n-1}{2}-6}\left(\frac{5n+3}{2}-2p+4\right)+2n-3+\sum_{k=2}^{4}(\frac{3n-1}{2}-2k+20)+(\frac{3n+1}{2}+18)$
= $n^{2}$ edges. Since no two edges in the same rique deviate from the
properties of cylindric layouts, it follows that the rique number of $k_{n,n}$
is at most $\lfloor\frac{n-1}{2}\rfloor-1$ when n is odd.

Case 2: $n$ is even. When $n$ is even, we prove that $K_{n,n}$ admits a rique
layout $\mathcal{L}$ with $\frac{n}{2}-2$ riques. Let
$A=\\{a_{1},\dots,a_{n}\\}$ and $B=\\{b_{1},\dots,b_{n}\\}$ be the two parts
of $K_{n,n}$, such that $a_{1}\prec b_{1}\prec a_{2}\prec b_{2}\prec\dots\prec
a_{\frac{n}{2}-1}\prec b_{\frac{n}{2}-1}\prec b_{\frac{n}{2}}\prec\dots\prec
b_{n}\prec a_{\frac{n}{2}}\prec\dots\prec a_{n}$ holds in $\mathcal{L}$. In
$\mathcal{L}$, there exist 12 special riques, in particular, the ones in
$\\{1,2,3,4,5,6,7,\frac{n}{2}-6,\frac{n}{2}-5,\frac{n}{2}-4,\frac{n}{2}-3,\frac{n}{2}-2\\}$;
see Fig. 46.

Page 1 of $\mathcal{L}$ contains the following $3n+1$ edges:

  * -

$\\{(a_{1},b_{j}),j=1,\dots,n\\}_{ht}$; dark red in Fig. 36,

  * -

$\\{(a_{i},b_{1}),i=\frac{n}{2},\dots,n\\}_{ht}$; red in Fig. 36,

  * -

$\\{(a_{\frac{n}{2}-1},b_{j}),j=2,\dots,\frac{n}{2}-1\\}_{hh}$; light blue in
Fig. 36,

  * -

$\\{(a_{i},b_{2}),i=\frac{n}{2},\dots,n\\}_{hh}$; light red in Fig. 36,

  * -

$\\{(a_{\frac{n}{2}},b_{j}),j=\frac{n}{2},\dots,n\\}_{hh}$; blue in Fig. 36.

Figure 36: Page $1$ of $\mathcal{L}$ when $n$ is even. Figure 37: Page $2$ of
$\mathcal{L}$ when $n$ is even.

Page 2 of $\mathcal{L}$ contains the following $\frac{5n}{2}+2$ edges:

  * -

$\\{(a_{i},b_{1}),i=2,\dots,\frac{n}{2}-1\\}_{ht}$; dark red in Fig. 37,

  * -

$\\{(a_{2},b_{\frac{n}{2}-1})\\}_{ht}$; orange in Fig. 37,

  * -

$\\{(a_{2},b_{j}),j=\frac{n}{2},\dots,n\\}_{ht}$; red in Fig. 37,

  * -

$\\{(a_{3},b_{n})\\}_{ht}$; light red in Fig. 37,

  * -

$\\{(a_{i},b_{3}),i=\frac{n}{2},\dots,n\\}_{ht}$;light blue in Fig. 37,

  * -

$\\{(a_{n-3},b_{j}),j=\frac{n}{2}-3,\dots,\frac{n}{2}+1\\}_{hh}$; blue in Fig.
37,

  * -

$\\{(a_{i},b_{\frac{n}{2}+1}),i=\frac{n}{2}+1,\dots,n-4\\}_{hh}$; dark blue in
Fig. 37,

  * -

$\\{(a_{\frac{n}{2}+1},b_{j}),j=\frac{n}{2}+2,\dots,n\\}_{hh}$; gray in Fig.
37.

For $p=3,4,5$, page $p$ of $\mathcal{L}$ contains the following
$\frac{5n}{2}+2$ edges

  * -

$\\{(a_{p-1},b_{j}),j=2,\dots,\frac{n}{2}-p+1\\}_{ht}$; dark red in Fig. 38,

  * -

$\\{(a_{p},b_{j}),j=\frac{n}{2}-p+1,\dots,n-p+2\\}_{ht}$; red in Fig. 38,

  * -

$\\{(a_{p+1},b_{j}),j=n-p+2,\dots,n\\}_{ht}$; light red in Fig. 38,

  * -

$\\{(a_{i},b_{p+1}),i=\frac{n}{2},\dots,n\\}_{ht}$; dark blue in Fig. 38,

  * -

$\\{(a_{n+p-6},b_{j}),j=\frac{n}{2}-3,\dots,\frac{n}{2}+p-1\\}_{hh}$; light
blue in Fig. 38,

  * -

$\\{(a_{i},b_{\frac{n}{2}+(p-1)}),i=\frac{n}{2}+(p-1),\dots,n+(p-6)\\}_{hh}$;
blue in Fig. 38,

  * -

$\\{(a_{\frac{n}{2}+(p-1)},b_{j}),j=\frac{n}{2}+p,\dots,n\\}_{hh}$; gray in
Fig. 38.

Figure 38: Page $p=3,4,5$ of $\mathcal{L}$ when $n$ is even.

Page 6 of $\mathcal{L}$ contains the following $\frac{5n}{2}-7$ edges:

  * -

$\\{(a_{5},b_{j}),j=2,\dots,\frac{n}{2}-5\\}_{ht}$; dark red in Fig. 39,

  * -

$\\{(a_{6},b_{j}),j=\frac{n}{2}-5,\dots,n-4\\}_{ht}$; red in Fig. 39,

  * -

$\\{(a_{7},b_{j}),j=n-4,\dots,n\\}_{ht}$; light red in Fig. 39,

  * -

$\\{(a_{i},b_{7}),i=\frac{n}{2},\dots,n\\}_{ht}$; dark blue in Fig. 39,

  * -

$\\{(a_{i},b_{\frac{n}{2}+5}),i=\frac{n}{2}+5,\dots,n)\\}_{hh}$; blue in Fig.
39,

  * -

$\\{(a_{\frac{n}{2}+5},b_{j}),j=\frac{n}{2}+6,\dots,n\\}_{hh}$; gray in Fig.
39.

Figure 39: Page $6$ of $\mathcal{L}$ when $n$ is even.

Page 7 of $\mathcal{L}$ contains the following $\frac{3n}{2}+23$ edges:

  * -

$\\{(a_{6},b_{j}),j=2,\dots,\frac{n}{2}-6\\}_{ht}$; dark red in Fig. 40,

  * -

$\\{(a_{7},b_{j}),j=\frac{n}{2}-6,\dots,n-5\\}_{ht}$; red in Fig. 40,

  * -

$\\{(a_{8},b_{j}),j=n-5,\dots,n\\}_{ht}$; light red in Fig. 40,

  * -

$\\{(a_{i},b_{8}),i=\frac{n}{2},\dots,n\\}_{ht}$; dark blue in Fig. 40,

  * -

$\\{(a_{\frac{n}{2}-1},b_{j}),j=\frac{n}{2},\dots,\frac{n}{2}+3)\\}_{hh}$;
gray in Fig. 40,

  * -

$\\{(a_{n-8},b_{j}),j=n-8,\dots,n\\}_{hh}$; blue in Fig. 40,

  * -

$\\{(a_{i},b_{n-8}),i=n-7,\dots,n\\}_{hh}$; light blue in Fig. 40.

Figure 40: Page $7$ of $\mathcal{L}$ when $n$ is even.

For $p=8,\dots,\frac{n}{2}-7$, page $p$ of $\mathcal{L}$ contains the
following $\frac{5n}{2}-2p+7$ edges:

  * -

$\\{(a_{p-1},b_{j}),j=2,\dots,\frac{n}{2}-p+1\\}_{ht}$; dark red in Fig. 41,

  * -

$\\{(a_{p},b_{j}),j=\frac{n}{2}-p+1,\dots,n-p+2\\}_{ht}$; red in Fig. 41,

  * -

$\\{(a_{p+1},b_{j}),j=n-p+2,\dots,n\\}_{ht}$; light red in Fig. 41,

  * -

$\\{(a_{i},b_{p+1}),i=\frac{n}{2},\dots,n\\}_{ht}$; dark blue in Fig. 41,

  * -

$\\{(a_{i},b_{\frac{n}{2}+p-2}),i=\frac{n}{2}+(p-2),\dots,n)\\}_{hh}$; blue in
Fig. 41,

  * -

$\\{(a_{\frac{n}{2}+(p-2)},b_{j}),j=\frac{n}{2}+(p-1),\dots,n\\}_{hh}$; light
blue in Fig. 41.

Figure 41: Page $p=8,\dots,\frac{n}{2}-7$ of $\mathcal{L}$ when $n$ is even.

Page $\frac{n}{2}-6$ of $\mathcal{L}$ contains the following 2n-2 edges:

  * -

$\\{(a_{\frac{n}{2}-7},b_{j}),j=2,\dots,\frac{n}{2}-8\\}_{ht}$; dark red in
Fig. 42,

  * -

$\\{(a_{\frac{n}{2}-6},b_{j}),j=\frac{n}{2}-8,\dots,n-7\\}_{ht}$; red in Fig.
42,

  * -

$\\{(a_{\frac{n}{2}-5},b_{j}),j=n-7,\dots,n\\}_{ht}$; light red in Fig. 42,

  * -

$\\{(a_{i},b_{\frac{n}{2}-5}),i=\frac{n}{2},\dots,n\\}_{ht}$; blue in Fig. 42,

  * -

$\\{(a_{i},b_{\frac{n}{2}-4}),i=\frac{n}{2}+5,\dots,n)\\}_{hh}$; dark blue in
Fig. 42.

Figure 42: Page $\frac{n}{2}-6$ of $\mathcal{L}$ when $n$ is even.

For $p=\frac{n}{2}-k,$ with $k\in\\{5,4,3\\}$, page $p$ of $\mathcal{L}$
contains the following $\frac{3n}{2}-2k+22$ edges:

  * -

$\\{(a_{p-1},b_{j}),j=2,\dots,\frac{n}{2}-p+1)\\}_{ht}$; dark red in Fig. 43,

  * -

$\\{(a_{p},b_{j}),j=\frac{n}{2}-p+1,\dots,n-p+2)\\}_{ht}$; red in Fig. 43,

  * -

$\\{(a_{p+1},b_{j}),j=n-p+2,\dots,n\\}_{ht}$; light red in Fig. 43,

  * -

$\\{(a_{i},b_{p+1}),i=\frac{n}{2},\dots,\frac{n}{2}+(k-1)\\}_{ht}$; pink in
Fig. 43,

  * -

$\\{(a_{i},b_{p+2}),i=\frac{n}{2}+(k-1),\dots,n-8+k\\}_{ht}$; light pink in
Fig. 43,

  * -

$\\{(a_{n-8+k},b_{j}),j=\frac{n}{2}-3-k,\dots,\frac{n}{2}\\}_{ht}$; blue in
Fig. 43,

  * -

$\\{(a_{i},b_{n+(2k-11)}),i=n-8+k,\dots,n\\}_{ht}$; light blue in Fig. 43,

  * -

$\\{(a_{i},b_{n+(2k-10)}),i=n-8+k,\dots,n\\}_{hh}$; dark blue in Fig. 43,

  * -

$\\{(a_{n-8+k},b_{j}),j=n+(2k-9),\dots,n\\}_{hh}$; gray in Fig. 43.

Figure 43: Page $p=\frac{n}{2}-k,$ with $k\in\\{5,4,3\\}$ of $\mathcal{L}$
when $n$ is even.

Page $\frac{n}{2}-2$ of $\mathcal{L}$ contains the following $\frac{3n}{2}+19$
edges:

  * -

$\\{(a_{\frac{n}{2}-2},b_{j}),j=2,\dots,\frac{n}{2}+4\\}_{ht}$; dark red in
Fig. 44,

  * -

$\\{(a_{\frac{n}{2}-1},b_{j}),j=\frac{n}{2}+4,\dots,n\\}_{ht}$; red in Fig.
44,

  * -

$\\{(a_{i},b_{\frac{n}{2}-1}),i=\frac{n}{2},\frac{n}{2}+1\\}_{ht}$; light red
in Fig. 44,

  * -

$\\{(a_{i},b_{\frac{n}{2}}),i=\frac{n}{2}+1,\dots,n-7\\}_{ht}$; pink in Fig.
44,

  * -

$\\{(a_{i},b_{n-7}),i=\frac{n}{4}+1,\dots,n\\}_{ht}$; dark blue in Fig. 44,

  * -

$\\{(a_{i},b_{n-6}),i=\frac{n}{4}+1,\dots,n\\}_{hh}$; light blue in Fig. 44,

  * -

$\\{(a_{\frac{n}{4}+1},b_{j}),j=n-5,\dots,n\\}_{hh}$; gray in Fig. 44,

  * -

$\\{(a_{\frac{n}{2}-3},b_{j}),j=2,3\\}_{hh}$; blue in Fig. 44.

Figure 44: Page $p=\frac{n}{2}-2$ of $\mathcal{L}$ when $n$ is even.

So, in total $\mathcal{L}$ has $n^{2}$ edges. Since no two edges in the same
rique deviate from the properties of cylindric layouts, it follows that the
rique number of $K_{n,n}$ is at most $\frac{n}{2}-2$ when n is even.

Figure 45: Illustration of the grid representation of a rique layout of
$K_{n,n}$ when $n$ is odd, in which paths of the same color correspond to the
same rique. The points of the grid that are covered by a solid (dashed) path
are head-head (head-tail, respectively). Here, the “special” pages are the
first (blue), second (violet), third (dark-purple), fourth (dark-green), fifth
(yellow), sixth (dark-gray), eighth (cyan), $\frac{n-1}{2}-5$ (green),
$\frac{n-1}{2}-4$ (purple), $\frac{n-1}{2}-3$ (turquoise), $\frac{n-1}{2}-2$
(brown), and $\frac{n-1}{2}-1$ (orange) when $n$ is odd. Figure 46:
Illustration of the grid representation of a rique layout of $K_{n,n}$ when
$n$ is even, in which paths of the same color correspond to the same rique.
The points of the grid that are covered by a solid (dashed) path are head-head
(head-tail, respectively). When $n$ is even, the “special” pages are the first
(blue), second (violet), third (dark-purple), fourth (dark-green), fifth
(yellow), sixth (dark-gray), eighth (cyan), $\frac{n}{2}-6$ (green),
$\frac{n}{2}-5$ (purple), $\frac{n}{2}-4$ (turquoise), $\frac{n}{2}-3$
(brown), and $\frac{n}{2}-2$ (orange).

∎

##  5 SAT formulation

In this section, we present a SAT formulation for the problem of testing
whether a given graph with $n$ vertices and $m$ edges admits a deque layout
with $p$ of deques; an implementation has already been incorporated in [5],
whose source code is available at https://github.com/linear-layouts/SAT.
However, before describing our formulation, we deem important to state that,
in [4], Bekos et al. have already presented a corresponding SAT formulation,
when the $p$ pages are riques. However, their approach heavily relies on the
fact that this specific type of linear layouts can be characterized by means
of a forbidden pattern in the underlying order (similar to the corresponding
ones for stack and queue layouts [7]). Given that dequeue layouts cannot be
characterized by means of such forbidden patterns in the underlying order, we
need a slightly different approach.

Similar to [4], our approach is an extension of the one in [7] for the stack
layout problem, in which there exist three different types of variables,
denoted by $\sigma$, $\phi$, and $\chi$, with the following meanings:  (i) for
a pair of vertices $u$ and $v$, variable $\sigma(u,v)$ is true, if and only if
$u$ is to the left of $v$ along the spine,  (ii) for an edge $e$ and a page
$i$, variable $\phi_{i}(e)$ is true, if and only if edge $e$ is assigned to
page $i$ of the book, and  (iii) for a pair of edges $e$ and $e^{\prime}$,
variable $\chi(e,e^{\prime})$ is true, if and only if $e$ and $e^{\prime}$ are
assigned to the same page.  Hence, there exist in total $O(n^{2}+m^{2}+pm)$
variables, while a set of $O(n^{3})$ clauses ensures that the underlying order
is indeed linear; for details see [7]. To overcome the issue that arises in
the absence of forbidden pattern, we introduce $4pm$ variables, such that
variable $\tau_{i}(e,x)$ with $x\in\\{hh,ht,th,tt\\}$ is true, if and only if
the type of edge $e$ at page $i$ is $x$. We ensure that each edge has at least
one of the allowed types, by introducing the following clause for each edge
$e$:

$\bigvee_{i=1}^{p}(\tau_{i}(e,hh)\vee\tau_{i}(e,ht)\vee\tau_{i}(e,th)\vee\tau_{i}(e,tt))$

With these variables, we can express different configurations that cannot
occur in a deque layout as clauses in the SAT formula. These clauses are
obtained by avoiding crossings between all edge types in the cylindric
representation of the graph. E.g., to express the different configurations
that cannot occur for a head-head edge $e=(u,v)$ and a head-tail edge
$e^{\prime}=(u^{\prime},v^{\prime})$, we introduce the following clause for
each page $i$ of the layout333Note that some parts of the clause appear only
certain conditions apply on the endpoints of $e$ and $e$’. These conditions
are listed next to the corresponding parts, such that if a condition is not
fulfilled, then the corresponding part has to be omitted.:

$\displaystyle\phi_{i}(e)\wedge\phi_{i}(e^{\prime})\wedge\tau_{i}(e,hh)\wedge\tau_{i}(e^{\prime},ht)$
$\displaystyle\rightarrow$
$\displaystyle~{}~{}~{}\neg(\sigma(u,u^{\prime})\wedge\sigma(u^{\prime},v)\wedge\sigma(v,v^{\prime}))\quad
u\neq v\neq u^{\prime}$
$\displaystyle~{}~{}~{}\wedge\neg(\sigma(v,u^{\prime})\wedge\sigma(u^{\prime},u)\wedge\sigma(u,v^{\prime}))\quad
u\neq v\neq u^{\prime}$
$\displaystyle~{}~{}~{}\wedge\neg(\sigma(u,v^{\prime})\wedge\sigma(v^{\prime},v)\wedge\sigma(v,u^{\prime}))\quad
u\neq v\neq v^{\prime}$
$\displaystyle~{}~{}~{}\wedge\neg(\sigma(v,v^{\prime})\wedge\sigma(v^{\prime},u)\wedge\sigma(u,u^{\prime}))\quad
u\neq v\neq v^{\prime}$
$\displaystyle~{}~{}~{}\wedge\neg(\sigma(u,u^{\prime})\wedge\sigma(u^{\prime},v^{\prime})\wedge\sigma(v^{\prime},v))\quad
u\neq u^{\prime}$
$\displaystyle~{}~{}~{}\wedge\neg(\sigma(u,v^{\prime})\wedge\sigma(v^{\prime},u^{\prime})\wedge\sigma(u^{\prime},v))\quad
u\neq v^{\prime}$
$\displaystyle~{}~{}~{}\wedge\neg(\sigma(v,u^{\prime})\wedge\sigma(u^{\prime},v^{\prime})\wedge\sigma(v^{\prime},u))\quad
v\neq u^{\prime}$
$\displaystyle~{}~{}~{}\wedge\neg(\sigma(v,v^{\prime})\wedge\sigma(v^{\prime},u^{\prime})\wedge\sigma(u^{\prime},u))\quad
v\neq v^{\prime}$

We introduce a clause similar to the one above for each pair of types of
edges, yielding in total $O(pm^{2})$ clauses. This completes the construction
of the formula. Note that the formulation can be easily adjusted for rique
layouts by introducing for each edge $e$ and each page $i$ the following
clause forbidding tail-head and tail-tail edges:
$\neg\tau_{i}(e,th)\wedge\neg\tau_{i}(e,tt)$.

Somehow unexpectedly, this simple adjustment was more efficient in practice
than the one by Bekos et al. [4], which is based on implementing the forbidden
pattern of rique layouts.

Findings. The implementation was extremely helpful, in general, for developing
all upper bounds of this paper. It further shows that the upper bound of
Theorem 5 is tight for all values of $n\leq 30$ (see Remark 1). Another
notable observation is that for $K_{n,n}$ it is possible to obtain a better
upper bound than the one of 1 (or in other words that $k$ deques are strictly
more powerful than $2k$ stacks): Our implementation shows that $K_{3n,3n}$
with $n\in\\{2,3,4,5\\}$ needs $n+1$ stacks, while the solver provided
solutions with $n$ deques for the corresponding values of $n$. Note that this
result would be implied (for any $n$) by Theorem 6, if the bound [12] on the
stack number of $K_{n,n}$ was shown to be tight.

##  6 Open Problems

In this paper, we presented bounds on the deque- and rique-numbers of complete
and complete bipartite graphs. We conclude with some open problems:

(i) We conjecture that the bound of Theorem 5 is tight.  (ii) As mentioned in
the introduction, the deque-number of planar graphs is $2$. We conjecture that
also their rique-number is $2$.  (iii) Another natural direction to follow is
to extend the study to other classes of graphs, as it is the case with the
corresponding stack- and queue-numbers.  (iv) Studying inclusion relationships
is also of interest, e.g., the class of graphs admitting 1-deques is not a
subclass of the class of graphs admitting 1-rique, 1-stack layouts, as a
maximal planar graph with a Hamiltonian path plus an edge belongs to the
former but not to the latter. What about the other direction?  (v) Related to
our research is also the problem of closing the gap between the lower bound of
$\lceil\frac{n}{2}\rceil$ and the upper bound of
$\lfloor\frac{2n}{3}\rfloor+1$ [12] on the stack number of $K_{n,n}$.

## References

  * [1] J. M. Alam, M. A. Bekos, M. Gronemann, M. Kaufmann, and S. Pupyrev.  The mixed page number of graphs.  Theor. Comput. Sci., 931:131–141, 2022.
  * [2] C. Auer.  Planar graphs and their duals on cylinder surfaces.  PhD thesis, Universität Passau, 2014.
  * [3] C. Auer, C. Bachmaier, F. Brandenburg, W. Brunner, and A. Gleißner.  Plane drawings of queue and deque graphs.  In U. Brandes and S. Cornelsen, editors, Graph Drawing, volume 6502 of LNCS, pages 68–79. Springer, 2010.
  * [4] M. A. Bekos, S. Felsner, P. Kindermann, S. G. Kobourov, J. Kratochvíl, and I. Rutter.  The rique-number of graphs.  In P. Angelini and R. von Hanxleden, editors, Graph Drawing and Network Visualization, volume 13764 of LNCS, pages 371–386. Springer, 2022.
  * [5] M. A. Bekos, M. Haug, M. Kaufmann, and J. Männecke.  An online framework to interact and efficiently compute linear layouts of graphs.  CoRR, abs/2003.09642, 2020.
  * [6] M. A. Bekos, M. Kaufmann, F. Klute, S. Pupyrev, C. N. Raftopoulou, and T. Ueckerdt.  Four pages are indeed necessary for planar graphs.  J. Comput. Geom., 11(1):332–353, 2020.
  * [7] M. A. Bekos, M. Kaufmann, and C. Zielke.  The book embedding problem from a sat-solving perspective.  In E. Di Giacomo and A. Lubiw, editors, Graph Drawing and Network Visualization, volume 9411 of LNCS, pages 125–138. Springer, 2015\.
  * [8] F. Bernhart and P. C. Kainen.  The book thickness of a graph.  J. Comb. Theory, Ser. B, 27(3):320–331, 1979.
  * [9] V. Dujmovic, D. Eppstein, R. Hickingbotham, P. Morin, and D. R. Wood.  Stack-number is not bounded by queue-number.  Comb., 42(2):151–164, 2022.
  * [10] V. Dujmovic, G. Joret, P. Micek, P. Morin, T. Ueckerdt, and D. R. Wood.  Planar graphs have bounded queue-number.  J. ACM, 67(4):22:1–22:38, 2020.
  * [11] V. Dujmović and D. R. Wood.  On linear layouts of graphs.  Discrete Mathematics & Theoretical Computer Science, 6(2):339–358, 2004.
  * [12] H. Enomoto, T. Nakamigawa, and K. Ota.  On the pagenumber of complete bipartite graphs.  J. Comb. Theory, Ser. B, 71(1):111–120, 1997.
  * [13] S. Felsner, L. Merker, T. Ueckerdt, and P. Valtr.  Linear layouts of complete graphs.  In H. C. Purchase and I. Rutter, editors, Graph Drawing and Network Visualization, volume 12868 of LNCS, pages 257–270. Springer, 2021.
  * [14] J. L. Ganley and L. S. Heath.  The pagenumber of $k$-trees is $O(k)$.  Discrete Applied Mathematics, 109(3):215–221, 2001.
  * [15] L. S. Heath, F. T. Leighton, and A. L. Rosenberg.  Comparing queues and stacks as mechanisms for laying out graphs.  SIAM J. Discrete Math., 5(3):398–412, 1992.
  * [16] L. S. Heath and A. L. Rosenberg.  Laying out graphs using queues.  SIAM J. Comput., 21(5):927–958, 1992.
  * [17] M. Hoffmann and B. Klemz.  Triconnected planar graphs of maximum degree five are subhamiltonian.  In M. A. Bender, O. Svensson, and G. Herman, editors, ESA, volume 144 of LIPIcs, pages 58:1–58:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [18] P. Jungeblut, L. Merker, and T. Ueckerdt.  A sublinear bound on the page number of upward planar graphs.  In J. S. Naor and N. Buchbinder, editors, ACM-SIAM SODA, pages 963–978. SIAM, 2022.
  * [19] D. J. Muder, M. L. Weaver, and D. B. West.  Pagenumber of complete bipartite graphs.  J. Graph Theory, 12(4):469–489, 1988.
  * [20] T. Ollmann.  On the book thicknesses of various graphs.  In F. Hoffman, R. Levow, and R. Thomas, editors, Southeastern Conference on Combinatorics, Graph Theory and Computing, volume VIII of Congressus Numerantium, page 459, 1973.
  * [21] A. Wigderson.  The complexity of the Hamiltonian circuit problem for maximal planar graphs.  Technical Report TR-298, EECS Department, Princeton University, 1982.
  * [22] M. Yannakakis.  Embedding planar graphs in four pages.  J. Comput. Syst. Sci., 38(1):36–67, 1989.
  * [23] M. Yannakakis.  Planar graphs that need four pages.  J. Comb. Theory, Ser. B, 145:241–263, 2020.