Forbidden Patterns in Mixed Linear Layouts

For an explicit description of the set $𝒫$ of patterns, we define a $k$-thick pattern to be obtained either from a $k$-twist by replacing each edge by a $k$-rainbow, or from a $k$-rainbow by replacing each edge by $k$-twist; see Figure 1 and Section 2.2 for a more elaborate introduction.

Note that Open Problem 3 asks for a characterization up to a function bounding the mixed page number depending on the size of the largest pattern occurring in the graph. That is, even if we know the size of the largest pattern, we do not learn the exact mixed page number but only an upper bound. A more granular characterization would guarantee the exact mixed page number given that a set of forbidden patterns is excluded. As a negative result, we present an infinite family of patterns that needs to be included in an obstruction set of graphs with mixed page number 2. Thus, Open Problem 3 does not admit such a precise answer.

When answering Open Problem 3, which we do positively for bounded-degree graphs, there is a trade-off between three objectives: First, the number of patterns should be small since each of them needs to be excluded to prove upper bounds. Second, the bound we obtain on the mixed page number should be small. And third, we want our results to hold for graph classes that are as large as possible, while smaller graph classes have the potential of better results in the first two objectives. In this subsection, we present explicit bounds on the mixed page number that are different trade-offs between these three objectives.

As a base for subsequent results, we start with (ordered) matchings having a separated layout and a relatively large obstruction set. Here, a layout of a bipartite graph is called separated if we first have all vertices of one part of the bipartition, and then all vertices of the other part. We provide an explicit list of the patterns in Section 2.1.

For stack layouts and queue layouts, it turned out to be a powerful tool to have only one pattern, namely twists, respectively rainbows. Close enough, we present two patterns, namely the two options for thick patterns, to play the same role for mixed linear layouts by combining twists and rainbows.

We finish the matching case by generalizing the separated layout to an arbitrary vertex ordering. We remark that we expect the patterns to always be matchings, as is the case with twists and rainbows, and even conjecture that the same set of patterns also works for general ordered graphs.

To prove this, we work with so-called quotients of linear layouts that can capture the global structure of an (ordered) graph and show how to transfer linear layouts of a quotient to the initial graph (Lemma 17), which might be of independent interest.

With Vizing’s theorem [76], all our results on matchings generalize to bounded-degree graphs, in particular we obtain the following bounds for Theorem 4.

Note that this is indeed a specification of Theorem 4 since the upper bound shows that if there is no large thick pattern, then the mixed page number is bounded, and conversely, if the mixed page number is bounded, there is no large thick pattern due to the lower bound.

Finally, we aim for the second objective to be optimal, i.e., we aim for an obstruction set such that the mixed page number is at most $k$ if and only if none of the forbidden patterns is contained. For $k=2$, we show that such a finite obstruction set exists if the ordered graph is bipartite and has a separated layout, but not in the general case.

For the negative side, we remark that it is not surprising that such an exact characterization is infeasible as no such characterization is known for stack layouts. Here, we know that an ordered graph without $k$-twist has stack number at most $O(k\log k)$ [17] and that this bound is tight [55]. However, one might think that with a larger obstruction set, an exact characterization is possible. For $k\ge 4$ this is not true [74] but to the best of our knowledge no explicit infinite family of patterns was known to be in the obstruction set. We provide constructions for the following theorem, which in particular proves Theorem 5 as all minimal patterns need to be included in the obstruction set. Here, minimal refers to edge-minimal for a given mixed page number (stack number), i.e., if any edge is removed, then the mixed page number (stack number) decreases.

As some theorems have only a proof sketch, we refer to [41] for the full paper.

Building on earlier notions [50, 64], the concepts of stack and queue number were first investigated by Bernhart and Kainen [12] in 1979 and Heath and Rosenberg [44] in 1992, respectively. Over the last three decades, there has been extensive research on these concepts leading to numerous results, primarily for planar graphs [2, 8, 9, 20, 22, 35, 65, 80, 81], but also for $1$-planar graphs [10] and graphs with bounded genus [42, 57] or bounded treewidth [56]. In light of our results it is worth mentioning that there is a particular interest in bounded-degree graphs [11, 78, 25]. In this context, the vertex ordering is usually not given, so there are two steps to solve: First one needs to find a good vertex ordering and second, the resulting ordered graph is analyzed, often using the characterization with twists and rainbows. In addition, the stack and queue number for directed acyclic graphs [43, 63, 48], where the vertex ordering must respect the orientation of the edges, have been studied fruitfully, e.g., for (planar) posets [62, 53, 4, 32, 69], or upward planar graphs [34, 49, 48].

Although Heath and Rosenberg [44] already suggested a study of mixed linear layouts back in 1992, specifically conjecturing that every planar graph has a $1$-stack $1$-queue layout, significant progress began only quite recently when Pupyrev [68] disproved their conjecture. Subsequently, other papers have followed strengthening Pupyrev’s result by showing that not even series-parallel [5] or planar bipartite graphs [35] admit a $1$-stack $1$-queue layout. Further investigations into more general mixed linear layouts have often been proposed [11, 63, 9]. Results on this include complete and complete bipartite graphs [3], subdivisions [24, 60, 68], and computational hardness results [19]. Very recently, Katheder, Kaufmann, Pupyrev, and Ueckerdt [51] related the queue, stack, and mixed page number to each other and asked for an improved understanding of graphs with small mixed page number both in the separated and in the general setting as, together with their results, this would fully reveal the connection between these three concepts. All these investigations have in common that it is quite difficult to analyze mixed linear layouts due to the lack of a simple characterization similar to rainbows and twists for stack and queue layouts, which is the gap we address in this paper.

An explicit investigation of rainbows and twists in linear layouts can be found from early on. In their seminal paper on queue layouts, Heath and Rosenberg [44] identified rainbows as a simple characterization for queue layouts. They showed that the queue number with respect to a fixed vertex order always equals the size of the largest rainbow, a result that has often been used to derive bounds on the queue number [22, 8, 4, 11, 27, 32, 2, 69, 53]. Similarly, twists offer a straight-forward characterization for stack layouts, although the stack number of an ordered graph is not exactly the size of the largest twist. While the the size of the largest twist is clearly a lower bound on the stack number, Davies [17] recently showed an upper bound of $𝒪(k\log k)$ on the stack number, where $k$ denotes the size of the largest twist. This very recent and asymptotically tight [55] bound, along with earlier larger upper bounds [40, 18, 55, 15] has proven useful for bounding the stack number of various graph classes [48, 63, 49, 34]. For small $k$, it is known that an order without a $2$-twist (that is, when $k=1$) corresponds to an outerplanar drawing of a graph, which is a $1$-stack layout. For $k=2$ (that is, an order without a $3$-twist), five stacks are sufficient and sometimes necessary [54, 1]; for $k=3$, it is known that $19$ stacks suffice [17].

Similarly, for the mixed page number we do not expect an exact characterization, but rather a characterization up to a function. For general graphs, previous results [74, 19] have shown that deciding whether an ordered matching has an $s$-stack $q$-queue layout is NP-complete for all $s\ge 4$ and $q\ge 0$, making the question for a finite set of patterns exactly characterizing $s$-stack $q$-queue layouts obsolete. However, in some special cases, such as for separated layouts of bipartite graphs or for smaller $s$ and $q$, there is still potential for an exact characterization, while in the general case we aim to find a finite characterization up to a function that is as small as possible.

Our investigations start with bipartite graphs having a separated layout, which is a setting that has been widely studied (sometimes, implicitly) under different names, such as 2-track layouts, 2-layer drawings, or partitioned drawings [16, 24, 3, 6, 79, 21, 28, 23, 29, 61, 70, 67]. Initially, we further narrow down our focus to matchings with a separated layout. Separated mathings can also be viewed as permutations of the right endpoints of the edges, relative to the order of the left endpoints. In this context, the mixed page number of the ordered matching equals the minimum number of monotone subsequences into which the permutation can be partitioned. For this problem it is known that permutations that can be partitioned into a fixed number of monotone subsequences, and thus matchings with a fixed mixed page number, are characterized by a finite, though potentially large set of forbidden subsequences [52, 31, 77].

Another related topic is the extremal theory of ordered graphs [72, 66], which has also been studied from the perspective of $0$-$1$-matrices in the case of bipartite graphs with a separated layout [71, 47, 58, 36, 38]. In this field, the focus is on determining how many edges (or $1$-entries) an ordered graph (or a $0$-$1$-matrix) can have while avoiding a specified family of patterns (or submatrices). A necessary condition for a set of patterns to characterize a fixed mixed page number is that these patterns must enforce the number of edges to be linear in the number of vertices. If the patterns are matchings, this necessary condition is met by the proof of the Füredi-Hajnal conjecture [36], which was proven by Marcus and Tardos [58].

Before proving our results in the subsequent sections, let us review linear layouts from different perspectives. We briefly state some connections here and refer to the full version [41] for a more detailed discussion.

Consider the grid representation of a bipartite graph $G$ with a fixed separated layout. That is, one part of the bipartition is represented by columns, the other by rows, and each edge is described by an $x$- and a $y$-coordinate indicating the column, respectively the row, of its endpoints. As we consider matchings, we have only one edge in each row and in each column. For two edges $e_1,e_2$ of $G$ we write $e_1\nearrow e_2$ if and , i.e., if $e_1$ and $e_2$ cross. Similarly, we write $e_1\searrow e_2$ if and $y(e_1)>y(e_2)$, i.e., if $e_1$ and $e_2$ nest. Consider a set of $k^2$ edges indexed by $e_{i,j}$ for $1\le i\le k$ and $1\le j\le k$. We say that the edges form a $k$-$⊞$-pattern if the following holds:

1. (i)

   $e_{i,j}\nearrow e_{i,j+1}$ for every $1\le i\le k$ and , and

2. (ii)

   $e_{i,j}\searrow e_{i+1,j}$ for every and $1\le j\le k$.

That is, in the grid representation we have $k$ increasing sequences of length $k$, where the $j$-th elements in each chain together form a decreasing sequence for each $j=1,\mathrm{\dots },k$. We denote the size of a $k$-$⊞$-pattern by $k\times k$ to indicate that we have $k^2$ edges, where $k$ is the parameter we are usually interested in. Notice that there are exactly four $⊞$-patterns of size $2\times 2$; see Figure 2.

As it turns out, $⊞$-patterns are deeply connected to mixed linear layouts. Our main result on $⊞$-patterns is summarized in the following theorem.

We translate Theorem 12 to the language of posets so we can use a result by Greene [39] to prove it in this regime. For this, we interpret a $⊞$-pattern, or more generally any matching $M$ with a separated vertex ordering, as a poset $P(M)$ whose elements are the edges of $M$. Since $M$ is a matching, for every two elements, $e_1,e_2$ of $P(M)$ with , it holds that either $e_1\nearrow e_2$ or $e_1\searrow e_2$. In the former case, we set in $P(M)$ and in the latter we make the two elements incomparable, for which we write $e_1\parallel e_2$. We call $P(M)$ the poset of $M$. Observe that a chain of $P(M)$ is increasing in the grid representation and corresponds to a twist in $M$, and an antichain is decreasing in the grid representation and corresponds to a rainbow. That is, to bound the mixed page number, we aim to cover each element of the poset by a chain or an antichain (or both) and thereby minimize the number of chains plus antichains.

Now, the lower bound of Theorem 12 asks for a proof that $P(M)$ cannot be covered by less than $k$ chains and antichains. The omitted proof of the following slightly stronger statement is straight-forward by counting the maximum number of elements in an (anti)chain.

That is, $⊞$-patterns are particularly hard graphs for mixed linear layouts as they do not profit from the possibility to mix chains and antichains, respectively queues and stacks, which makes them a suitable candidate for a characterization. The remainder of this subsection is devoted to the upper bound of Theorem 12, which confirms that these candidates are, up to a factor of 2, the only reason for a large mixed page number.

The upper bound relies on insights into a Ferrer’s diagram, a standard combinatorial tool [30], that represents how many elements can be covered by a certain number of chains, respectively antichains. In general, a Ferrer’s diagram represents a partition of an integer by left-aligned rows of cells, where a summand $s$ is represented by a row of length $s$ and the rows are ordered by decreasing length from bottom to top. In our context, we partition the number $|P|$ of elements of a poset. Roughly speaking, the Ferrer’s diagram of a poset $P$ consists of $|P|$ cells arranged in such a way that the number of cells in the first $i$ rows is the number of elements in $P$ that can be covered by $i$ chains, and the number of cells in the first $i$ columns equals the number of elements that can be covered by $i$ antichains. It is proved by Greene [39] that such diagrams exist. We refer readers not familiar with this kind of Ferrer’s diagrams, sometimes also called Greene’s diagrams, to the full version [41, Section 2.1] and also point to Figure 3 (right) for an example.

For Theorem 12, we want a bound depending on the size of the largest $⊞$-pattern, so we first need to identify these patterns in the Ferrer’s diagrams. Let us first discuss why this is not a trivial task. Recall that the Ferrer’s diagram only indicates the number of elements that can be covered by a certain number of (anti)chains but does not associate the cells with elements of the poset as this is not always possible. For an example, consider Figure 3 where we have three rows of size 5, 3, and 1 but there is no chain decomposition with chains of lengths 5, 3, 1. That is, there is no way of writing elements into all cells of the diagram such that elements in the same row form a chain. Therefore, we cannot simply use the “elements in the $k\times k$-square” to identify a $k$-$⊞$-pattern.

Instead, besides the translation of the linear layout problem to posets and its Ferrer’s diagrams, the core of the proof of Theorem 12 is a counting argument that allows to identify a $⊞$-pattern of the same size as the largest square in the Ferrer’s diagram. Having this, we may use $2k$ (anti)chains, where $k$ is the size of the largest square instead of the $⊞$-pattern, which can be done using the properties of a Ferrer’s diagram (see full version [41, Section 2.1]). Finally, we remark that Theorem 12 is tight (see full version [41, Lemma 18]) and yields a 2-approximation in $O(n^{3/2}\log n)$ [73, 33].

Having Theorem 12, we can characterize which patterns cause a large mixed page number up to a factor of 2. In contrast to stack layouts and queue layouts, however, we have not only a single pattern like twists or rainbows, respectively, but a family of patterns. Note that all $k$-$⊞$-patterns are necessary to forbid if we want an exact characterization as they all have mixed page number $k$. In this section, we give up the idea of an (almost) exact characterization in favor of reducing the number of patterns we forbid. More precisely, we point out two specific $⊞$-patterns whose absence characterizes the mixed page number up to a polynomial factor.

As we may use both stacks and queues in mixed linear layouts, we combine twists and rainbows to obtain two new patterns for characterizing the mixed page number. A $t$-thick $k$-twist is obtained from a $k$-twist by replacing each edge by a $t$-rainbow. That is, we have $k$ pairwise vertex-disjoint $t$-rainbows, where each edge nests with the edges belonging to the same rainbow but crosses the edges of all other rainbows, see Figure 4 (left). Similarly, a $t$-thick $k$-rainbow is obtained from a $k$-rainbow by replacing each edge by a $t$-twist, see Figure 4 (right). In both cases, we call $t$ the thickness and write the size as $k\times t$ to emphasize that we have $kt$ edges organized as $k$ smaller groups of size $t$. Throughout the paper, we often have $t=k$ and simply write $k$-thick rainbow, respectively $k$-thick twist. If we mean any of the two patterns, we say $k$-thick pattern.

In this section, we investigate the relation between thick patterns and $⊞$-patterns. Specifically, we show that thick patterns occur if and only if $⊞$-pattern occur, where the sizes are tied by a polynomial function. Together with Theorem 12 we obtain:

Note that the lower bound is already given by Theorem 12, so our task is to bound the mixed page number in terms of the largest thick pattern. Theorem 12 also gives an upper bound using $⊞$-patterns instead of thick patterns, so we aim to show that if there is a large $⊞$-pattern, than there also is a large thick pattern.

The proof makes use of the grid representation, which is subdivided repeatedly. First, after each subdivision, we find a sufficiently large $⊞$-pattern, and second these smaller patterns can be combined to a thick pattern. See the full version [41, Lemma 19] for the proof.

A separated matching $G$ corresponds to a permutation $\pi (G)$. The separated mixed page number of a matching $G$ equals the minimum number of monotone subsequences that $\pi (G)$ can be partitioned into. In this setting the following is known: permutations that can be partitioned into a fixed number of monotone subsequences are characterized by a finite set of forbidden subsequences [52, 31, 77]. Thus, for every pair $(s,q)$, there exists a finite number of $(s,q)$-critical matchings with a fixed separated layout. For separated non-matchings our main result is that there is only a finite number of $2$-critical graphs.

On the way to proving this, we additionally show that if the maximum degree of all $(s,q)$-critical graphs is bounded, then the total number of $(s,q)$-critical graphs must be finite. Further, we show that if the number of $(s,q)$-critical graphs is bounded for all pairs $(s,q)$ with $s+q=k$, then the number of $k$-critical graphs is bounded. Therefore, to show that the number of $k$-critical graphs is finite, not only for $k=2$ but for arbitrary $k$, it suffices to show that the maximum degree of all $(s,q)$-critical graphs is bounded. Then, for $(1,1)$-critical graphs, we show that the maximum degree is indeed bounded, so we can conclude that the number of $(1,1)$-critical graphs is finite.

Before proving Theorem 20, we remark that a similar characterization of graphs with a bounded separated pure stack (queue) number is straightforward. In fact, there exists a single $(s,0)$-critical graph and a single $(0,q)$-critical graph for all $s,q\ge 1$. In contrast, characterizations for mixed linear layouts are significantly more complex. We computationally identified all $9$ graphs that are $1$-critical, all $20$ graphs that are $(1,1)$-critical, and all $3128$ graphs that are $2$-critical.

Our proof uses essentially the same arguments as [77] to show that if the maximum degree in an $(s,q)$-critical graph $G$ is bounded, then the total number of edges of $G$ is bounded. The key in the arguments in [77] is that partial Boolean functions, interpreted as an assignment of the edges of a subgraph to the set of stacks or to the set of queues, can be combined to a total Boolean function corresponding to the given graph. See the full version [41, Section 4.1] for details.

The following lemma is the result of these arguments and potentially useful for proving that the number of $(s,q)$-critical graphs is finite for arbitrary $s$ and $q$. For this, it now suffices to show that the maximum degree in every $(s,q)$-critical graph is bounded.

Additionally, the following lemma allows us to extend results on $(s,q)$-critical graphs to more general $k$-critical graphs. Specifically, it shows that if the number of $(s,q)$-critical graphs is bounded for all pairs $(s,q)$ with $s+q=k$, then the number of $k$-critical graphs is also bounded. The proof is not surprising and also inspired by [77] so we refer to the full version [41, Lemma 22]

Note that in the separated case there is exactly one $(2,0)$-critical graph – a $3$-twist – and exactly one $(0,2)$-critical graph – a $3$-rainbow. Moreover, the following lemma, together with Lemma 21, shows that the number of $(1,1)$-critical graphs is also bounded. Applying Lemma 22, it then follows that the number of $2$-critical graphs is finite. With Lemma 21, the only thing that is left to finish Theorem 20 is to prove that the maximum degree in any $(1,1)$-critical graph is bounded.

The following proof sketch is worked out more detailed in the full version [41, Lemma 24].

Based on the literature, we first observe that the number of critical graphs characterizing non-separated $s$-stack $q$-queue layouts is expected to be infinite even for matchings, for $s\ge 4$. To this end, we use a hardness result stating that it is NP-complete to recognize $4$-stack layout for matchings with a fixed layouts (from coloring circle graphs) [74]. Moreover, an already NP-complete mixed linear layout recognition problem with given vertex ordering remains NP-complete under addition of a stack or queue [19]. Thus, deciding whether a matching with a given vertex ordering admits an $s$-stack $q$-queue layout is NP-complete for all $s\ge 4$ and $q\ge 0$. On the other hand, a finite forbidden set of critical graphs implies a poly-time recognition, which would contradict the two mentioned hardness results under the assumption that $P\ne \text{NP}$. However, it is still interesting to construct an explicit infinite set of critical graphs, for fixed $k=s+q$, especially for where the state of the art does not give whether or not the obstruction set is finite. In the following, we construct such an infinite set of $(s,0)$- and $2$-critical graphs for $s\ge 2$.

As a first step, we give an infinite obstruction set for layouts with $s=2,q=0$. We use edges such that the conflicting edges (that cannot share a stack) form an odd-length cycle; clearly, the cycle requires three colors (stacks). In the full version [41, Lemma 25] this is generalized to an infinite obstruction set for all pure stack layouts with stack number at least 2.

Observe that Theorem 24 does not rule out a possibility of a finite obstruction set for mixed linear layouts with $\mathrm{mn}=2$. The next theorem closes this gap.