Linear Layouts of Graphs with Priority Queues

The wide range of applications of linear layouts and the fact that they have been restricted so far to unweighted graphs, naturally motivate extensions of the notion of linear layout to edge-weighted graphs. For example, in scheduling applications, the edges of a graph can represent processes, each with an associated priority; each vertex $v$ of the graph enforces that all processes corresponding to edges incident to $v$ begin simultaneously; among the running processes, those with higher priority must be completed first. Edge weights can also model constraints in other classical applications of linear layouts, such as logistics networks modelled as switchyard networks [34, 37], where adjacent edges represent containers that must be pushed or popped simultaneously across different storage locations. The weight of an edge corresponds to the weight of its container, and it may be necessary to ensure that containers stacked on top of others are lighter.

We introduce a model called priority queue layout, or simply PQ-layout. This model utilizes priority queues for the storage of edges assigned to the same page, where the edge weights correspond to the priorities (i.e., keys) for the data structure. As for stack and queue layouts, in a PQ-layout all vertices of the graph lie on a horizontal line $\mathrm{\ell }$, and the edges are assigned to different priority queues according to a left-to-right sweep of $\mathrm{\ell }$. When an edge $e$ is dequeued, it must have the minimum priority among the edges stored in the same priority queue as $e$. See Figure 1(d) for an example, and refer to Section 2 for a formal definition of our model. Note that, unlike stack and queue layouts, our model allows edges in the same page to cross or properly nest, provided that they have suitable weights.

Following a current focus of research on linear layouts, we mainly study the priority queue number of edge-weighted graphs, that is, the number of pages required by their PQ-layouts:

(i) We provide non-trivial upper and lower bounds for the priority queue number of complete graphs (Section 3). (ii) We characterize the graphs that have priority queue number 1, regardless of the edge-weight function (Section 4). (iii) We investigate the priority queue number of graphs with bounded pathwidth and bounded treewidth (Section 5). (iv) We prove that deciding whether an edge-weighted graph has priority queue number $k$ (for a non-fixed integer $k$) is $\mathrm{𝖭𝖯}$-complete if the linear ordering of the vertices is fixed (Section 6).

We remark that, as far as we know, there is only one previous study in the literature about using linear layouts of edge-weighted graphs [7]; however, this study uses edge weights to further restrict stack layouts. For space restrictions, proofs of statements marked with a (clickable) ($\star$) are omitted or sketched. We provide the missing proofs in the full version [20].

Choose an arbitrary ordering of the vertices $v_1\prec \mathrm{\cdots }\prec v_n$ and define the sets (priority queues) ${𝒫}_1,\mathrm{\dots },{𝒫}_{n-1}$. For each $j\in \{2,\mathrm{\dots },n\}$, assign all edges whose right endpoint is $v_j$ to ${𝒫}_{j-1}$. Clearly, no forbidden configuration occurs, independent of the edge-weight function. $◀$

Next, we consider bipartite graphs, that is, the graphs whose vertex sets are the union of two disjoint independent sets $A$ and $B$. In the literature on linear layouts, separated linear layouts, where vertices of $A$ precede the vertices of $B$ or vice versa, have been considered for bipartite graphs [25]. The separated priority queue number $\mathrm{spqn}(G)$ of a bipartite graph $G$ is the minimum $k$ such that, for any edge-weight function, there is a PQ-layout $\mathrm{\Gamma }$ that is a separated linear layout and $\mathrm{pqn}(\mathrm{\Gamma })=k$. We can easily determine the separated priority queue number of the complete bipartite graph $K_{n,n}$. At the end of this section, we will use the separated priority queue number to give a lower bound on the priority queue number of complete and complete bipartite graphs.

First observe that $\mathrm{spqn}(K_{m,n})\le \min \{m,n\}$: place the vertices of the larger set, say $A$, before the vertices of the smaller set, say $B$. Then, independent of the edge weight function, for each vertex $b\in B$, all edges ending at $b$ can be assigned to a separate page.

To show $\mathrm{spqn}(K_{m,n})\ge \min \{m,n\}$, assume w.l.o.g. that the vertices in $A$ precede the vertices in $B$. Consider an edge weight function where, at every vertex $b\in B$, each edge weight in $\{1,2,\mathrm{\dots },\min \{m,n\}\}$ occurs at least once among $b$’s incident edges. In any bipartite PQ-layout $\mathrm{\Gamma }$ of $K_{m,n}$, denote the vertices of $B$ by $b_1,b_2,\mathrm{\dots }$ in the order they appear along the spine. In $\mathrm{\Gamma }$, $b_1$ is incident to an edge with weight $\min \{m,n\}$, $b_2$ is incident to an edge with weight $\min \{m,n\}-1$, etc., $b_{\min \{m,n\}}$ is incident to an edge of weight 1. This is a $\min \{m,n\}$-inversion requiring at least $\min \{m,n\}$ pages. $◀$

Theorem 2 also provides an upper bound for the (non-separated) priority queue number of $K_{n,n}$. Next, we give a corresponding linear lower bound showing that $\mathrm{pqn}(K_{n,n})\in \mathrm{\Theta }(n)$.

For $K_{n,n}$, we define an edge-weight function $w$ that has, at each vertex, for every $i\in \{1,\mathrm{\dots },n\}$, exactly one incident edge of weight $i$.¹¹1In contrast to the proof of Theorem 2, we cannot arbitrarily assign weights to edges incident to each vertex $b\in B$ because this may give twice the same edge weight at a vertex of partition $A$. To this end, we partition the edge set into $n$ perfect matchings $M_1,\mathrm{\dots },M_n$, and, for each edge $e\in M_i$, we set $w(e)=i$.

For any PQ-layout $\mathrm{\Gamma }$ of $⟨K_{n,n},w⟩$, we can find a sublayout ${\mathrm{\Gamma }}^{\prime }$ that is a bipartite PQ-layout of $⟨K_{\frac{n}{2},\frac{n}{2}},w⟩$ – either take the first $\frac{n}{2}$ vertices of $A$ and the last $\frac{n}{2}$ vertices of $B$ or vice versa.²²2For simplicity, we assume that $n$ is even.

Note that we cannot directly apply Theorem 2 to ${\mathrm{\Gamma }}^{\prime }$ because we have already fixed an edge-weight function. Instead, we analyze the possible distribution of the edge weights incident to vertices in ${\mathrm{\Gamma }}^{\prime }$ by a representation as a black-and-white grid;³³3A similar, although not identical, representation is used by Alam et al. [36] to prove the mixed page number of $K_{n,n}$. see the the full version [20] for an illustration and a more extensive description. Our grid has $\frac{n}{2}$ columns that represent the vertices of the latter partition (in order from left to right as they appear in ${\mathrm{\Gamma }}^{\prime }$) and it has $n$ rows that represent the edge weights $\{1,\mathrm{\dots },n\}$ (in order from bottom to top). A grid cell in column $i$ and row $j$ is colored black if the $i$-th vertex is incident to an edge of weight $j$, and it is colored white otherwise. Observe that, in this grid, a strictly monotonically decreasing path of black cells having length $k$ is equivalent to a $k$-inversion in ${\mathrm{\Gamma }}^{\prime }$. We can show that there always exists such a path of length $\lceil \frac{3-\sqrt{5}}{4}n\rceil$: the candidates for being the first black cell of the path are those who do not have another black cell in their top left region of the grid. We find these cells, color them white and iteratively repeat this process to find the candidates for being the second, third, etc. black cell of the path. We can prove that we need at least $\lceil \frac{3-\sqrt{5}}{4}n\rceil$ iterations until the grid is white. $◀$

Since $K_n$ contains $K_{\lfloor \frac{n}{2}\rfloor ,\lfloor \frac{n}{2}\rfloor }$ as a subgraph, Theorem 3 immediately implies a linear lower bound on $\mathrm{pqn}(K_n)$:

We may assume w.l.o.g. that $G=(V,E)$ is edge-maximal of pathwidth $p$, i.e., $G$ is an interval graph with clique number $\omega (G)=p+1$ [15]. Let ${\{I_v=[a_v,b_v]\}}_{v\in V}$ be an interval representation of $G$ with distinct interval endpoints. In particular $b_u\ne b_v$ for any $u\ne v\in V$.

We take the ordering $v_1,\mathrm{\dots },v_n$ of vertices given by their increasing right interval endpoints. That is, . Crucially, for any with $v_i{v}_k\in E$, also $v_j{v}_k\in E$.

To define the partition of $E$ into $p+1$ priority queues ${𝒫}_1,\mathrm{\dots },{𝒫}_{p+1}$, we consider a proper vertex coloring of $G$ with $\chi (G)=\omega (G)=p+1$ colors. This exists, as $G$ is an interval graph. Now for $c=1,\mathrm{\dots },p+1$ let ${𝒫}_c$ be the set of all edges in $G$ whose right endpoint in the vertex ordering has color $c$. In fact, each ${𝒫}_c$ contains none of the forbidden configurations in Figure 2, and hence is a priority queue independent of the edge-weights, since in each forbidden configuration in Figure 2 there would be an edge in $G$ between the right endpoints $v_r$ and $v_{r^{\prime }}$ of the two edges $e$ and $e^{\prime }$ forming the forbidden configuration. But this would imply different colors for $v_r$ and $v_{r^{\prime }}$ and therefore different priority queues for $e$ and $e^{\prime }$. $◀$

We remark that Corollary 4 implies that there are graphs with pathwidth $p$ and priority queue number at least $\lfloor \frac{3-\sqrt{5}}{8}(p+1)\rfloor$ as $K_{p+1}$ has pathwidth $p$.

Next, we shall construct for every integer $p\ge 1$ a graph $G=G_p$ of treewidth $2$ together with edge weights $w$ so that every vertex ordering $\sigma$ of $G$ contains a $p$-inversion. If every vertex ordering of $⟨G,w⟩$ contains a $p$-inversion, then $\mathrm{pqn}(G,w)\ge p$ and hence $\mathrm{pqn}(G)\ge p$.

Let $p\ge 1$ be a fixed integer. Our desired graph $G_p$ will be a rooted $2$-tree, i.e., an edge-maximal graph of treewidth $2$ with designated root edge, which are defined inductively through the following construction sequence:

• $\mathrm{■}$

  A single edge $e^{\ast }=v^{\prime }{v}^{\prime \prime }$ is a $2$-tree rooted at $e^{\ast }$.

• $\mathrm{■}$

  If $G$ is a $2$-tree rooted at $e^{\ast }$ and $e=uv$ is any edge of $G$, then adding a new vertex $t$ with neighbors $u$ and $v$ is again a $2$-tree rooted at $e^{\ast }$. We say that $t$ is stacked onto $uv$.

We define a vertex ordering $\sigma$ of a $2$-tree rooted at $e^{\ast }=v^{\prime }{v}^{\prime \prime }$ to be left-growing if no vertex (different from $v^{\prime }$, $v^{\prime \prime }$) appears to the right of both its parents. First we show that it is enough to force a $p$-inversion (and hence $\mathrm{pqn}(G)\ge p$) in every left-growing vertex ordering.

Intuitively, whenever in the construction sequence of $G$ a vertex $t$ is stacked onto an edge $uv$, in $\tilde{G}$ we instead stack $p^2$ “copies” of $t$ called $t_1,\mathrm{\dots },t_{p^2}$ onto $uv$ (treating each $t_i$ like $t$ henceforth). The weights $\tilde{w}(u{t}_i)$ and $\tilde{w}(v{t}_i)$, $i=1,\mathrm{\dots },p^2$, are chosen very close to $w(ut)$ and $w(vt)$ but increasing with $i$ for $u{t}_i$ and decreasing with $i$ for $v{t}_i$. This way, if all $p^2$ copies of $t$ lie right of $u$ and $v$, we get a $p$-inversion among the $u{t}_i$’s or $v{t}_i$’s. $\mathrm{⊲}$

We then construct a sequence $⟨H_1,w_1⟩,⟨H_2,w_2⟩,\mathrm{\dots }$ of edge-weighted rooted $2$-trees, so that for every $k$, every left-growing vertex ordering of $⟨H_k,w_k⟩$ contains a $k$-inversion. The construction of $⟨H_k,w_k⟩$ is recursive, starting with $⟨H_1,w_1⟩$ being just a single edge of any weight. For $k\ge 2$, we start with $d=k^2$ vertices $a_1,\mathrm{\dots },a_d$ stacked onto the root edge $e^{\ast }=v^{\prime }{v}^{\prime \prime }$, and stacking a vertex $b_i^{\prime }$ onto each $v^{\prime }{a}_i$, as well as a vertex $b_i^{\prime \prime }$ onto $v^{\prime \prime }{a}_i$ for $i=1,\mathrm{\dots },d$. All these edges have weight $0$. Then, each $b_i^{\prime }{a}_i$ and $b_i^{\prime \prime }{a}_i$ is used as the base edge of two separate copies of $⟨H_{k-1},w_{k-1}⟩$, where however the edge-weights $w_{k-1}$ of each copy are scaled and shifted to be in a specific half-open interval $[x,y)\subset ℝ$ depending on the current base edge ($b_i^{\prime }{a}_i$ or $b_i^{\prime \prime }{a}_i$). See Figure 5 for an illustration.

By induction, there is a $(k-1)$-inversion in each such copy of $H_{k-1}$. Using the pigeon-hole principle, and the Erdős–Szekeres theorem, we then identify an edge $a_i{v}^{\prime }$ (or $a_i{v}^{\prime \prime }$) which forms a $k$-inversion either together with $(k-1)$-inversion of one copy of $H_{k-1}$, or with $k-1$ edges, each from the $(k-1)$-inversion of a different copy of $H_{k-1}$.

To finish the proof, it is then enough to take $⟨H_p,w_p⟩$ as constructed above, and then apply Claim 22 to obtain the desired edge-weighted $2$-tree $⟨G_p,w_p⟩$ with $\mathrm{pqn}(G_p,w_p)\ge p$. $◀$

As graphs of treewidth $2$ are always planar graphs, we conclude with the following result that contrasts similar results for the queue and stack number [23, 43]:

We observe that $H_k$ in the proof of Theorem 21 contains $4$ copies of $H_{k-1}$ while $H_1$ contains $2$ vertices. Thus, there are at least $4^p$ vertices in $G:=H_p$, which has treewidth $p$. $◀$

Containment in $\mathrm{𝖭𝖯}$ is clear as we can check in polynomial time whether a given assignment of edges to $k$ priority queues corresponds to a valid PQ-layout.

We show $\mathrm{𝖭𝖯}$-hardness by reduction from the problem of coloring circular-arc graphs, which is known to be $\mathrm{𝖭𝖯}$-complete if $k$ is not fixed [27]. A circular-arc graph is the intersection graph of arcs of a circle (see Figure 6 on the left), that is, the arcs are the vertices and two vertices share an edge if and only if the corresponding arcs share a point along the circle.

For a given circular-arc graph $H$, we next describe how to obtain an edge-weighted graph $⟨G,w⟩$ and a vertex ordering $\sigma$ such that a $k$-coloring of $H$ directly corresponds to a PQ-layout of $⟨G,w⟩$ under $\sigma$ with $k$ priority queues. Without loss of generality, we assume that we have a circular-arc representation of $H$ where all endpoints of the arcs are distinct.

We “cut” the circle at some point, which gives an interval representation where some vertices $S$ of $H$ refer to two intervals; in Figure 6, the circular arcs $a$, $b$, and $d$ are cut into intervals $a_1$ and $a_2$, $b_1$ and $b_2$, and $d_1$ and $d_2$, respectively. We let the endpoints of all intervals be the vertices of $G$, whose ordering $\sigma$ along the spine is taken from the ordering of the corresponding endpoints of the intervals (for the intervals belonging to $S$, the order is arbitrary). Further, for each interval, we have an edge in $G$ connecting its two endpoints. To obtain $w$, we assign to the edges of $G$ the numbers 1 to $m$, where $m=|V(H)|+|S|$, in decreasing order of the right endpoints of the intervals. This way, every pair of edges whose corresponding intervals share a common point need to be assigned to distinct priority queues.

So far, there is no mechanism that assures that $a_1$ and $a_2$, $b_1$ and $b_2$, etc., are assigned to the same priority queue. To this end, we add, for each such pair $⟨a_1,a_2⟩$, an edge from the left endpoint of $a_1$ to the right endpoint of $a_2$. We call these $|S|$ new edges synchronization edges, and we assign them the weights $m+1,\mathrm{\dots },m+|S|$ in decreasing order of their right endpoints. Furthermore, we add $k-1,k-2,\mathrm{\dots }$ heavy edges below the leftmost, second leftmost, … vertex on the spine, respectively, as well as, $k-1,k-2,\mathrm{\dots }$ heavy edges below the rightmost, second rightmost, … vertex on the spine, respectively, see Figure 6. Clearly, $k\ge |S|$, otherwise we have a no-instance. The heavy edges have distinct right endpoints and their weights are chosen such that (i) they are greater than $M$, where $M=m+|S|$ is the largest weight used so far, and (ii) they are chosen in decreasing order from left to right such that each pair of heavy edges needs to be assigned to distinct priority queues if they overlap.

Consider the vertices of $G$ from the outside to the inside. At the outer endpoint of $a_1$ ($a_2$, resp.), the edge $a_1$ ($a_2$, resp.) and the synchronization edge get the same color by the pigeonhole principle because all but one priority queue is occupied by the heavy edges and the previously considered edges, which all induce pairwise forbidden configurations. $\mathrm{⊲}$

If we have a PQ-layout of $⟨G,w⟩$ under vertex ordering $\sigma$ with $k$ priority queues, we obtain, due to the choice of $w$ and $\sigma$, a coloring of $H$ by using the priority queues as colors. In particular, due to Claim 25, both parts of the “cut” circular arcs get the same color. Conversely, we can easily assign the edges of $⟨G,w⟩$ to $k$ priority queues if we are given a $k$-coloring of $H$. Clearly, our reduction can be implemented to run in polynomial time.$◀$