Linear Layouts Revisited:
Stacks, Queues, and Exact Algorithms

A linear layout $⟨\prec ,\sigma ⟩$ of a graph $G$ is a total ordering $\prec$ of its vertices and a partitioning $\sigma$ of its edges into $k$ pages such that each page satisfies certain conditions. The two by far most commonly studied types of linear layouts are stack layouts and queue layouts; in the former, we require that no four vertices $a\prec b\prec c\prec d$ have the edges $ac$ and $bd$ placed on the same page, while for the latter we forbid any page from containing the edges $ad$ and $bc$. Intuitively, this corresponds to forbidding edges crossing and edges nesting (in a rainbow pattern), respectively – see Figure 1. ^††Due to space constraints, we defer full proofs of statements marked with ★ to the full version [14].

Originally motivated from applications in VLSI [10, 41] and bioinformatics [31], stack and queue layouts have become the focus of extensive research. While there are many classical works studying the structural properties of the two notions [32, 46, 34, 19, 18, 20, 21, 17], several more recent studies have targeted exact and parameterized algorithms for computing stack and queue layouts that minimize the number of used pages. These results are inherently aimed at circumventing the long-known intractability of these problems: the $\mathrm{𝖭𝖯}$-hardness of determining whether an input graph admits a $2$-page stack layout or a $1$-page queue layout has been established over thirty years ago [46, 34].

To that end, recent works have pursued the use of structural graph parameters to establish tractability on graphs which are “well-structured”. Computing $\mathrm{\ell }$-page stack layouts is now known to be fixed-parameter tractable w.r.t. the vertex cover number [7] or, alternatively, the feedback edge number of the input graph $G$ [26]. Computing $\mathrm{\ell }$-page queue layouts is likewise known to admit a fixed-parameter algorithm w.r.t. the vertex cover number of $G$ [8]. One drawback of these results is that they only yield tractability under highly restrictive graph parameters, in the sense of achieving low values only on very “simple” graphs. While computing $1$-page queue layouts is also known to be fixed-parameter tractable when parameterized by the treedepth of $G$ [8], for general $\mathrm{\ell }$ it was repeatedly posed as an open question whether the aforementioned vertex-cover based algorithms can be lifted to less restrictive structural graph parameters [21, 7, 25, 8, 26]. Another recent direction is the establishment of tighter algorithmic upper bounds for special cases: while $\mathrm{\ell }$-page stack and queue layouts can both be computed in time $n^{𝒪(n)}$ via trivial brute-force algorithms, $2$-page stack layouts are now known to admit a subexponential algorithm [26].

For an integer $\mathrm{\ell }\ge 1$ we let $[\mathrm{\ell }]$ denote the set $\{1,2,\mathrm{\dots },\mathrm{\ell }\}$. We assume the reader to be familiar with standard graph terminology [15]. Without loss of generality, we assume all input graphs to be connected, have $n$ vertices and $m$ edges. For a set of vertices $V^{\prime }\in V(G)$, we let $G[V^{\prime }]$ denote the graph induced on $V^{\prime }$. Furthermore, for a set of edges $E^{\prime }\in E(G)$, we let $V(E^{\prime })$ denote the set of its endpoints and $G[E^{\prime }]=(V(E^{\prime }),E^{\prime })$. A cut $(A,B)$ of $G$ is a partition of the vertices in $A\subseteq V(G)$ and $B=V(G)\setminus A$. We call $F=\{uv\in E(G)\mid u\in A,v\in B\}$ a cut-set of size $\left|F\right|$ that induces the cut $(A,B)$. Throughout the paper, we omit an explicit reference to $G$ if it is clear from the context, e.g., we write $V$ and $E$ instead of $V(G)$ and $E(G)$.

Given a linear order $\prec$ of a graph $G$ and two vertices $u,v\in V$, we say that $u$ is left of $v$ if $u\prec v$ and right of $v$ if $v\prec u$. The vertices $u$ and $v$ are consecutive on the spine if they occur consecutively in $\prec$, i.e., there is no vertex $w\in V$ such that $u\prec w\prec v$ or $v\prec w\prec u$ holds. We address with ${\text{Left}}_v^{\prec }≔\{u\in V\mid u\prec v\}$ all vertices $u\in V$ left of $v$ with respect to $\prec$ and define ${\text{Right}}_v^{\prec }≔V\setminus ({\text{Left}}_v^{\prec }\cup \{v\})$. Finally, we let $X_v^{\prec }≔\{uw\in E\mid u\in {\text{Left}}_v\cup \{v\},w\in {\text{Right}}_v\}$ denote the set of edges that span the spine between $v$ and its right neighbor, i.e., all edges with one endpoint left of (or at) $v$ and one right of $v$.

We assume familiarity with the basic foundations of parameterized complexity theory [11]. All algorithms obtained in this work are exact, deterministic, constructive and rely exclusively on computable functions. To express some of our bounds, we will occasionally use the Knuth notation $\uparrow \uparrow$ where for an integer $z$, $2\uparrow \uparrow z$ represents an exponential tower of $2$’s of height $z$.

In this section, we obtain a fixed-parameter algorithm that takes as input a positive integer $\mathrm{\ell }$ and a graph $G$, is parameterized by $\mathrm{\ell }+\text{vi}(G)$ and computes an $\mathrm{\ell }$-page stack and/or queue layout of $G$ (or both), if such layouts exist. We begin by noting that using well-known relationships between vertex integrity, minimum-page stack and queue layouts and the graph parameter treewidth (tw), we can assume $\mathrm{\ell }$ to be upper-bounded by a function of $\text{vi}(G)$ thanks to the well-known relation $\text{tw}(G)\le \text{vi}(G)$:

The algorithm operates by obtaining a problem kernel, as formalized below; recall $p=\text{vi}(G)$.

Lemma 5 directly implies Theorem 1, and the rest of this section is dedicated to proving this lemma. For the following, let us fix a graph $G$, positive integers $\mathrm{\ell }$ and $p$, and a choice of $S\subseteq V(G)$ witnessing $\text{vi}(G)=p$ as in Section 2. Further let $𝒞$ be the set of connected components of $G-S$. First, we define a notion of “component-types” which groups components in $𝒞$ that exhibit the same outside connections and internal structure.

We now introduce the notion of large equivalence classes based on their size. We then use this to define what we call a large group of vertices – one that contains exactly one representative from each large equivalence class. Our kernel will keep a bounded number of these large groups.

Next we define a special induced subgraph that will serve as our kernel. The definition is based on carefully choosing a $k$ that is bounded by a computable function of $p$ and $\mathrm{\ell }$ so that keeping only $k$ many $k$-large groups along with the small parts of the graph suffices to capture the necessary structure. Towards this, let us first fix $f(\mathrm{\ell },p,x):=2^{2^{\mathrm{\ell }\cdot x^2\cdot 2^{12p^2}}}$ to be a computable function that is large enough to apply our Ramsey-type arguments later on; here, $x$ will be an integer that represents the size of a deletion set (initially $S$, but this will be updated iteratively in the proof of Lemma 11). Moreover, let $g(\mathrm{\ell },p)$ be a computable function of $\mathrm{\ell }$ and $p$ that will upper-bound our nested application of the function $f$ in that same proof; to provide a concrete bound, we set $g(\mathrm{\ell },p):={(2\uparrow \uparrow (p\cdot 2^{2p^2})\cdot 2+4)}^{\mathrm{\ell }\cdot p}$.

Intuitively, the reduced graphs we will be dealing with will consist of $S$, a set $S^{\prime }$ of all equivalence classes of $\sim$ which are too small to fully saturate our large groups (these will later be treated essentially in the same way as $S$), and a sufficient number of large groups; equivalence classes of size larger than $f(\mathrm{\ell },p,x)$ are “pruned” to have size exactly $f(\mathrm{\ell },p,x)$. A schematic overview of this intuition can be found in Figures 2b and c later on.

The core of our result is the following lemma, which we prove separately in Section 3.1.

Before proceeding to that proof, we show how to construct a reduced graph having size bounded by a computable function of $p$ and $\mathrm{\ell }$ in polynomial time.

Lemma 11 combined with Lemma 10 establishes Lemma 5 by constructing a reduced graph which is a kernel of the desired size. Thus, what remains is to establish Lemma 10; this is where the core ideas of Ramsey pruning will come into play.

In this section, we present an algorithm to decide if a given graph $G$ has a stack (or queue) layout on $\mathrm{\ell }$ pages and with page width $q$, i.e., an $\mathrm{\ell }$-page $q$-width linear layout, in $n^{𝒪(q\cdot \mathrm{\ell })}$ time. In the affirmative case, it can also output such a layout. Since only little adaption is required between stack and queue layouts, we only discuss problem specific changes where necessary. We will first give an intuitive overview over our approach and the core ideas to showing its correctness, details can be found in Sections 4.2 and 4.1 and the full version.

In this section, we show that we can find a one-page queue layout, if it exists, in $2^{𝒪(n)}$ time, which improves on the trivial algorithm that exhaustively considers all $n!$ possible spine orders. Our algorithm exploits the equivalence between one-page queue layouts and arched leveled planar embeddings established by Heath and Rosenberg [34]. We first show that we can reduce the problem of deciding whether a graph admits a one-page queue layout to deciding whether at least one of $2^{𝒪(n)}$ labeled instances of Arched Leveled Planarity admits a solution. While Arched Leveled Planarity is $\mathrm{𝖭𝖯}$-complete [34], our labeled instances can be solved in linear time thanks to a reduction to the well-studied problem Level Planarity [35, 36]. We will assume that $G$ is connected (as each component can be treated separated) and, as $G$ must be planar [34], we assume $\left|E\right|=𝒪(n)$.

We translate the definition of Heath and Rosenberg [34] into moderns terms as follows. Graph $G$ has a leveled planar embedding if there exists a level assignment function $\gamma :V\to [h]$ that maps each $v\in V$ to one of $h\ge 1$ levels, and a straight-line planar drawing $\mathrm{\Gamma }$ of $G$ such that each vertex $v$ has y-coordinate $\gamma (v)$ and all edges are proper, i.e., for all $uv\in E$ we have $\left|\gamma (u)-\gamma (v)\right|=1$. The latter property allows us to express the drawing as a collection of total orders ${\prec }_i$, one for each level $i\in [h]$, that specifies the left-to-right order of the vertices on level $i$ [36]. For each level $i$, let $s_i$ be the rightmost vertex on level $i$ in $\mathrm{\Gamma }$ such that we have $s_{i}w\in E$ for some $w\in V$ with $\gamma (w)=i+1$, or if there is no such vertex, let $s_i$ be the leftmost vertex on level $i$. Arched leveled planar embeddings extend leveled planar embeddings by also allowing non-monotone arching edges $t_{i}w$ between the leftmost vertex $t_i$ on level $i$ and vertices $w\in V$ with $\gamma (w)=i$ and $s_i{⪯}_{i}w$ [34]. These edges can be drawn crossing-free below the lowest level; see Figure 7b. The problem Arched Leveled Planarity asks whether $G$ has a level assignment that admits an arched leveled planar embedding. Heath and Rosenberg [34] showed that the spine order of a one-page queue layout of a graph $G$ induces a level assignment together with a vertex order on each level that together yield an arched leveled planar embedding of $G$ and vice versa; see Figure 7.

We show that, when seeking a one-page queue layout of $G$, one can branch over the information needed to infer the level assignment for a corresponding arched leveled planar embedding. Consider an arbitrary orientation of the edge set $E$ as an oriented arc set $A$ and let $\delta :A\to \{\uparrow ,\curvearrowright \}$ be a function that determines if an arc $uv\in A$ should be ordinary ($\uparrow$) or arching ( $\curvearrowright$ ). The tuple $ℒ=(A,\delta )$ is called a labeling of $G$; see also Figure 7c. A level assignment $\gamma$ is said to be consistent with $ℒ$ if and only if, for every $uv\in A$, it holds $\gamma (u)=\gamma (v)-1$ if $\delta (uv)=\uparrow$ and $\gamma (u)=\gamma (v)$ if $\delta (uv)=\curvearrowright$. Similarly, an embedding $\mathrm{\Gamma }$ is consistent with $ℒ$ if its level assignment is consistent and we have $u{\prec }_{\gamma (u)}v$ for every $uv\in {\delta }^{-1}(\curvearrowright )$. Clearly, every arched leveled planar embedding $\mathrm{\Gamma }$ of $G$ induces a labeling $(A_{\mathrm{\Gamma }},{\delta }_{\mathrm{\Gamma }})$ that is consistent with $\mathrm{\Gamma }$. Conversely, we can reobtain $\mathrm{\Gamma }$ from this $(A_{\mathrm{\Gamma }},{\delta }_{\mathrm{\Gamma }})$ by fixing an arbitrary vertex to level 0, performing a BFS from $v$ using the direction information in $A_{\mathrm{\Gamma }}$ to determine levels for all other vertices above and below, and potentially shifting all assigned levels such that their numbers span the same range as those in $\mathrm{\Gamma }$. This is formalized by the following lemma.

To now decide if a given graph $G$ has an arched leveled planar embedding $\mathrm{\Gamma }$, we can branch over all $𝒪(4^n)=2^{𝒪(n)}$ different labelings $ℒ=(A,\delta )$ of $G$. In each branch, we use Lemma 26 to compute a level assignment ${\gamma }_{ℒ}$ or immediately reject the branch. Thus, it remains to check in each branch, i.e., for each level assignment, if $G$ admits a corresponding arched leveled planar embedding. We do so using a linear-time reduction to the problem Level Planarity, which requires a level assignment as part of its input but does not allow arching edges. We emulate arching edges in Level Planarity as follows (see also Figure 8). First, we enclose the whole graph in a frame, which is a cycle spanning from below its lowest level to above its highest that will have a unique embedding (up to reflection) and for which we ensure that the remaining graph is drawn inside of it. Between each pair of levels $i,i+1$, we add a level $i+0.5$ and subdivide all edges to ensure properness. We use $l_i$ and $r_i$ to refer to the two vertices of the frame cycle that are on level $i+0.5$. Replace each arching arc $uv\in A$ with $\delta (uv)=\curvearrowright$ on level $i$ with the edges $u{l}_{i-1}$, $u{l}_i$, and $v{r}_i$ to $G^{\prime }$; see Figure 8. Observe that this forces $u$ to become the leftmost vertex on level $i$ and $v$ to be right of any vertex adjacent to one on level $i+1$. We provide a formal construction and show equivalence in the full version [14]. Using the known algorithm for testing Level Planarity in linear time [35, 36], we finally obtain our third contribution.

While our results improve the state of the art on computing linear layouts in several directions, they also highlight the prominent open questions in this area. In particular, Theorem 1 moves us closer to settling the long-standing open questions of whether treewidth or treedepth can be used to facilitate the computation of linear layouts [21, 7, 25, 8, 26]. At the same time, Theorems 2 and 3 yield the question of whether these classical problems can be solved in single-exponential time.