Upward Partitioned Book Embeddings

Abstract

We analyze a directed variation of the book embedding problem when the page partition is prespecified and the nodes on the spine must be in topological order (upward book embedding). Given a directed acyclic graph and a partition of its edges into k pages, can we linearly order the vertices such that the drawing is upward (a topological sort) and each page avoids crossings? We prove that the problem is NP-complete for $k\ge 3$, and for $k\ge 4$ even in the special case when each page is a matching. By contrast, the problem can be solved in linear time for $k=2$ pages when pages are restricted to matchings. The problem comes from Jack Edmonds (1997), motivated as a generalization of the map folding problem from computational origami.

1 Introduction

Book Embeddings. Bernhart and Keinen [BK79] first introduced the concept of book embeddings and book thickness of graphs in 1979. Since then, book embeddings and book thickness have been widely studied as natural geometric invariants in directed and undirected graphs with applications in graph drawing and graph algorithms. Book embeddings (also studied under the name of stack layouts [CLR87, HP97, HPT99, HP99]) have applications in VLSI design, fault-tolerant processing, parallel process scheduling, sorting networks, and parallel matrix computations [CLR87, HLR92, HR92].

Given an undirected graph $G=(V, E)$, where $|V| = n$ and $|E| = m$, a book embedding consists of

• 1. a linear ordering $\pi$ of the vertices V, defining an embedding of the vertices into the spine (a line in the plane); and

• 2. a disjoint partition of the edges E into sets, so that each set of the partition can be embedded into a page (half-plane bounded by the spine) without intersection between the edges on each page.

The pages join together at the spine to form a book. The book thickness of a graph G is the minimum number k of pages in any book embedding of G.

Much of the previous research on book embedding (on undirected graphs) focuses on the book thickness of particular graph classes such as complete bipartite graphs [ENO97] and planar graphs (which have an upper bound of 4 pages) [Yan89, BBKR15, BGR16]. Graphs of book thickness 1 turn out to have a simple characterization as (exactly) outerplanar graphs [BK79], and such graphs can be recognized in linear time [Wie86]. By contrast, graphs with a 2-page book embedding are exactly the sub-Hamiltonian graphs [BK79], and recognizing such graphs is NP-complete [Wig82].

Directed Graphs. Motivated by many of the same applications, book embedding has been generalized to directed graphs. For directed acyclic graphs (DAGs), an upward book embedding is a book embedding such that the linear ordering of the vertices on the spine is in topological order [HP99, HPT99]. For general digraphs, oriented book embeddings [MK16] require that all arcs embedded into a page (or the spine) must agree in orientation (pointed up or down with respect to the order on the spine).

Research in upward book embedding includes combinatorial results for classes of DAGs such as trees, cycles, or paths by using characteristics of the underlying undirected graph [HP99]. Furthermore, more recent research studied the book embedding of directed planar graphs [FFR11]. As in the undirected case, there is a linear-time algorithm to determine whether a DAG has a 1-page upward book embedding [HP99] (although the algorithm is very different from the 1-page book embedding algorithm applied to the DAG’s underlying undirected graph). Furthermore, determining whether a DAG has a 6-page upward book embedding is NP-complete [HP99]. There is a linear-time algorithm for 2-page upward book embedding of planar directed series-parallel graphs [DGDLW06]. Note that undirected series-parallel graphs are necessarily sub-Hamiltonian. For graphs with cycles, oriented book embeddings and oriented book thickness have been found for several graph classes including cycles and oriented trees [MK16].

See [DW04, DW05] for more detailed citations lists and surveys about book embeddings and linear graph layouts for both directed and undirected graphs.

Partitioned Problem. In the partitioned book embedding problem, we are given the partition of edges into pages. This variation eliminates one of the previous combinatorial aspects of finding a book embedding (namely finding the partition of edges), and leaves only finding the vertex order on the spine. Intuitively, this problem should be simpler. Indeed, there is a linear-time algorithm for determining whether a given edge partition can result in a 2-page book embedding of an undirected graph [HN14, ABD12]. Nonetheless, the partitioned k-page book embedding problem is NP-complete for undirected graphs where $k \ge 3$ [ALN15]. In their proof, the gadgets only work with undirected edges and therefore cannot directly be applied to upward book embedding.

In terms of partitioned book embedding problems where the edges in a partition form a matching, [Hos12] showed that for undirected graphs, it is NP-hard to find the ordering of vertices given unbounded number of pages (i.e. unbounded number of partitions). Although the reduction in [Hos12] is also from Betweenness (defined in Definition 1), the techniques used are simpler and different from ours since they consider undirected graphs and allow unbounded number of partitions of edges.

Table 1. Summary of known and new results in partitioned book embedding. New results are written in bold.

Our Results. In this paper, we study the natural combination of the partitioned variation (where we are given the partition of edges into pages) with upward book embedding of DAGs, which has not been considered before (Upward Partitioned k -Page Book Embedding). We prove that the resulting problem is NP-complete for any $k \ge 3$. Our hardness proof techniques also apply to a special case of this problem, called Upward Matching-Partitioned k -Page Book Embedding, where only disjoint edges map to each page (forming a matching). For this special case, we show NP-hardness for $k \ge 4$ and that book embedding can be solved in linear time for $k=1$ page or $k=2$ pages. Table 1 puts these results in context with previous results.

Upward Matching-Partitioned 4-Page Book Embedding is in fact motivated by the (nonsimple) map folding problem, posed by Jack Edmonds in 1997 (personal communication with E. Demaine); see [ABD+04, DLM12]. Edmonds showed that the problem of finding a flat folded state of an $m \times n$ grid crease pattern, with specified mountains and valleys, reduces to exactly this type of book embedding problem, with the $k=4$ pages corresponding to the four compass directions of a square. Furthermore, $1 \times n$ and $2 \times n$ map folding reduce to the problems with $k=2$ and $k=3$ pages. Algorithms for solving Upward Matching-Partitioned k -Page Book Embedding are thus of particular interest because they solve the long-standing map folding open problem as well.

In Sect. 2, we formally define our book embedding models. In Sect. 3, we prove NP-completeness for Upward Partitioned 3-Page Book Embedding. Finally, in Sect. 4, we show that Upward Matching-Partitioned Book Embedding can be solved in linear time for 2 pages and is NP-complete for 4 pages.

2 Definitions

We define the Upward Partitioned k -Page Book Embedding (UPBE- k) problem similarly to the definition for Partitioned k -Page Book Embedding as given in [ALN15]. Specifically, we are given a directed acyclic graph (DAG) $G=(V, E)$ and a partition of the edges in E: $P = \left\{ E_1, E_2, \dots , E_k\right\}$ where $E_1 \dot{\cup } E_2 \dot{\cup } \cdots \dot{\cup } E_k = E$, where $\dot{\cup }$ denotes disjoint union. The goal is to determine whether G can be embedded in a k-page book such that the ordering $\pi$ of the vertices on the spine is topologically sorted and each $E_i \in P$ lies in a separate page.

The Upward Matching-Partitioned k -Page Book Embedding (UMPBE- k) problem is the special case of UPBE- k in which every edge partition $E_i \in P$ forms a directed matching, that it, has at most one edge incident to each vertex in G.

For a given upward partitioned book embedding instance $G=(V, E, P)$, let $\pi$ represent a valid ordering of V on the spine where a valid ordering is one that satisfies the constraints on every page (e.g. non-crossing edges) and follows topological order. As stated previously, $\pi$ is also a valid topological sorting of V. We write $\pi (x) < \pi (y)$ (resp., $\pi (x) > \pi (y)$) if node $x\in V$ comes earlier/before (resp., later/after) $y\in V$ in $\pi$. For ease of wording, we will assign colors to edge partitions and refer to edges within each partition to have a particular color.

3 UPBE is NP-Complete

We show that UPBE- k is NP-hard via a reduction from the NP-complete problem Betweenness. The problem Betweenness is defined as follows.

Definition 1

( Betweenness [Opa79]). We are given a set L of n elements and a set C of m ordered triples where each member of a triple is a member of L. Let $\phi$ be a total ordering of the elements in L. An ordered triple, $\langle a, b, c \rangle \in C$ is satisfied if either $\phi (a)< \phi (b) < \phi (c)$ or $\phi (c)< \phi (b) < \phi (a)$ is true. The goal is to find an ordering $\phi$ such that all ordered triples in C are satisfied.

Given an instance (L, C) of Betweenness, we construct an instance, $G=(V, E)$, with edge partition, $P = \left\{ \texttt {Red}, \texttt {Green}, \texttt {Blue}\right\}$, of UPBE-3 such that a subsequence of a solution $\pi$ corresponds to a valid ordering $\phi$ of L in the Betweenness instance. For each element $x\in L$, we create vertices $x_1,\ldots , x_{2m - 1}$ in V. We call these vertices the element vertices. Our reduction uses two types of gadgets: ordered triple gadgets and order preserving gadgets. Their function is to enforce a betweenness constraint given by an element of C and to ensure that the order of element vertices of subscript j in $\pi$, with $j\in \{1,\ldots , 2m - 2\}$, is the reverse order of element vertices of subscript $j+1$, respectively. We prove that (G, P) admits an upward book embedding given by $\pi$ if and only if the order of element vertices of the same subscript in $\pi$ corresponds to a solution $\phi$ for the (L, C) Betweenness instance.

3.1 Gadgets

Ordered Triple Gadget. We order the set C arbitrarily. For the $(\frac{i+1}{2})$-th ordered triple $\langle a, b, c \rangle \in C$, where i is an odd integer between and including 1 and $2m-1$, we construct an ordered triple gadget that enforces the betweenness constraint on the triple of element vertices $a_{i}, b_{i}, c_{i}$ in $\pi$. Specifically, we create the following nodes and edges.

Definition 2

(Ordered Triple Gadget). Let (L, C) be an instance of Betweenness. Order the set C arbitrarily. For the $\left( \frac{i+1}{2}\right)$-th ordered triple $\langle a, b, c\rangle$, where i is an odd integer between and including 1 and $2m-1$, construct nodes $l_i$, $\alpha _i$, $\omega _i$, $a'_i$, $b'_i$, $c'_i$, and $h_i$. Then, create directed edges $(l_i, \alpha _i), (l_i, \omega _i) \in \mathtt {Red}$, $(\alpha _i, a_i'), (\alpha _i, b_i'), (\omega _i, b_i'), (\omega _i, c_i') \in \mathtt {Blue}$, and $(a_i', h_i), (b_i', h_i), (c_i', h_i) \in \mathtt {Green}$.

Refer to Fig. 1 for an example construction. Nodes $a_{i}', b_{i}'$ and $c_{i}'$ are respectively connected to $a_{i}'', b_{i}''$ and $c_{i}''$ by an edge in Red (where $a_i''$, $b_i''$, and $c_i''$ are part of the order preserving gadget defined in Definition 3). The topologically earliest and latest nodes in the gadget are respectively $l_i$ and $h_i$. The choice between $\pi (a'_{i})<\pi (b'_{i})<\pi (c'_{i})$ and $\pi (a'_{i})>\pi (b'_{i})>\pi (c'_{i})$ (and hence the choice between $\pi (a_i)< \pi (b_i) < \pi (c_i)$ and $\pi (a_i)> \pi (b_i) > \pi (c_i)$) is encoded in the choice between $\pi (\alpha _{i})<\pi (\omega _{i})$ and $\pi (\alpha _{i})>\pi (\omega _{i})$ as we prove in Lemmas 1 and 2.

Fig. 1.

Ordered triple gadget (left) and order preserving gadget for odd i (center) and for even j (right). The red edges from $a_i'$, $b_i'$ and $c_i'$ from the ordered triple gadget lead to $a_i''$, $b_i''$, and $c_i''$ in the order preserving gadget. The red edge from $h_i$ directs to $r_i$. (Color figure online)

Fig. 2.

The two possible embeddings of the ordered triple gadget. (Color figure online)

Lemma 1

Given a positive instance (G, P) containing the ordered triple gadget shown in Fig. 1 (left), if $\pi (h_i)< \min (\pi (a_i''), \pi (b_i''), \pi (c_i''))$ then either $\pi (a_i'')< \pi (b_i'') < \pi (c_i'')$ or $\pi (c_i'')< \pi (b_i'') < \pi (a_i'')$.

Proof

Notice that $h_i$ must appear after $a_i'$, $b_i'$ and $c_i'$ due to topological order. By the assumption in the lemma, $h_i$ be before $a_i''$, $b_i''$, $c_i''$ respectively. We first prove that $\min (\pi (a_i'), \pi (b_i'), \pi (c_i')) > \max (\pi (\alpha _i), \pi (\omega _i))$, i.e., no vertex in the gadget must occur between $\alpha _i$ and $\omega _i$. Because of the topological order, $\pi (b_i') > \max (\pi (\alpha _i), \pi (\omega _i))$. Suppose $\pi (\alpha _i)<\pi (\omega _i)$ (see Fig. 2 (top)). By topological order $\pi (c_i') > \pi (\omega _i)=\max (\pi (\alpha _i), \pi (\omega _i))$. If $\pi (a_i') < \pi (\omega _i)$, since $\pi (\omega _i)<\pi (a_i'')$, the red edges $(a_i', a_i'')$ and $(l_i, \omega _i)$ would intersect, a contradiction. The case when $\pi (\alpha _i)>\pi (\omega _i)$ is symmetric.

Trivially, either $\pi (\alpha _i) < \pi (\omega _i)$ or $\pi (\alpha _i) > \pi (\omega _i)$. We first assume $\pi (\alpha _i) < \pi (\omega _i)$ (Fig. 2 (top)). Then $\pi (c_i')< \pi (b_i') < \pi (a_i')$, or else at least one pair of blue edges ($(\alpha _i, b_i')$, $(\alpha _i, a_i')$, $(\omega _i, c_i')$, $(\omega _i, b_i')$) would cross. Since all red edges $(a_i',a_i''), (b_i',b_i'')$ and $(c_i',c_i'')$ nest around $h_i$, every pair of such edges must be nested. Therefore, $\pi (a_i'')< \pi (b_i'') < \pi (c_i'')$. The case when $\pi (\alpha _i)>\pi (\omega _i)$ is symmetric.     $\square$

Order Preserving Gadget. By Lemma 1, each ordered triple gadget enforces a betweenness constraint on vertices $a_i''$, $b_i''$ and $c_i''$. The order preserving gadgets serve two purposes: ensuring that the i-th betweenness constraint is enforced in the i-th copy of element vertices; and ensuring that each copy of element vertices must occur in the reverse order of its predecessor. That implies that every other copy of element vertices occur in exactly the same order. We build $2m - 1$ order preserving gadgets, the j-th gadget containing $x_j$ for each $x\in L$.

Definition 3

(Order Preserving Gadget). For each odd i in the range $[1, 2m-1]$, we build the following nodes and edges:

• 1. Nodes $a_i'', b_i'', c_i''$, $x^p_i$ for $p \in [1, n]$, and $r_i$.

• 2. Directed edges $(a_i'', a_i), (b_i'', b_i), (c_i'', c_i) \in \mathtt {Red}$.

• 3. Directed paths of length 7 connecting $r_i$ to $x^p_i$ for all $p \in [1, n]$ and where $x^p_i \ne a_i, b_i, c_i$. The paths alternate between red and green edges.

• 4. Directed paths of length 7 connecting $r_i$ to $a''_i$, $b''_i$, and $c''_i$ with alternating red and green edges.

For each even j in the range $[1, 2m-1]$, we build the following nodes and edges:

• 1. Nodes $x^p_j$ for $p \in [1, n]$ and $r_j$.

• 2. Directed edges $(x^p_j, r_j) \in \mathtt {Red}$ for all $p \in [1, n]$.

The gadget is divided into two parts: the elements part containing the element vertices, and the order preserving tree whose root is labeled $r_i$ or $r_j$. Figure 1 (center) shows an example of an order preserving gadget containing element vertices with odd subscript. Such instances are connected to ordered triple gadgets by three incoming red edges and have the vertex $r_i$ as the lowest vertex in the topological order. The dashed edges represent a path of length 7 of alternating red/green edges that are connected to the element vertex $x_i$ if $x\in L$ is not in the $\left( \frac{i+1}{2}\right)$-th ordered triple, or connected to the vertex $x_i''$ otherwise. The vertices $x_i''$ for an element x in the i-th ordered triple are then connected to the element vertex $x_i$ by a blue edge. For gadgets that contain element vertices with even subscript j (Fig. 1 (right)), $r_j$ is the highest vertex in the topological order. For even $j\in \{2,\ldots ,2m-2\}$, we connect $x_j$ to $x_{j-1}$ with a blue edge and $x_j$ to $x_{j+1}$ with a green edge, for all $x\in L$ (see Fig. 6).

For odd i, the order preserving tree consists of n paths of length 7 of alternating red/green edges connected to the i-th element vertex (represented in Fig. 1 (center) as dashed arrows). Informally, their purpose is to allow such paths to “cross” the vertices connected to the i-th ordered triple gadget by red edges, while $r_i$ as the first vertex in the topological order of the order preserving gadget.

Lemma 2

Let (G, P) be a positive instance containing an order preserving gadget of odd index i connected to an ordered triple gadget representing $\langle a,b,c\rangle$. If there exists a set of blue edges $(s_{i-1},x_i)$, $\pi (s_{i-1})<\pi (r_i)$ and $\pi (s_{i-1}) < \min (\pi (a_i'', b_i'', c_i''))$, from some vertices $s_{i-1}$ for all $x\in L$, then either $\pi (a_i)<\pi (b_i)<\pi (c_i)$ or $\pi (a_i)>\pi (b_i)>\pi (c_i)$.

Proof

By topological order, $\pi (r_i)<\pi (x_i)$ for all $x\in L$. Then, all blue edges of the form $(s_{i-1},x_i)$ must nest around $r_i$. By Lemma 1, the order of vertices $a_i''$, $b_i''$ and $c_i''$ must obey the betweenness constraint $\langle a,b,c\rangle$. Since $\pi (y_i'')>\pi (r_i), y\in \{a,b,c\}$, if $\pi (a_i'')<\pi (b_i'')$ then $\pi (a_i)<\pi (b_i)$ or else edges $(a_i'', a_i)$ and $(s_{i-1}, b_i)$ would cross. With similar arguments, we can show that the order of the i-th element vertices must obey the betweenness constraint $\langle a,b,c\rangle$.    $\square$

Lemma 3

Let (G, P) be a positive instance containing three subsequent order preserving gadgets with indices $j-1$, j, and $j+1$ where j is an even integer in $\left\{ 2, \dots , 2m - 2\right\}$. If $\pi (r_{j}) < \min \{\pi (r_{j-1}), \pi (r_{j+1})\}$, the element vertices with subscript $j+1$ appear in $\pi$ in the same order as the element vertices with subscript $j-1$.

Proof

We prove that the order of the element vertices with subscript $j-1$ is the reverse order of the element vertices with subscript j in $\pi$. By a similar argument, we can then show the same for j and $j+1$, completing the proof. Notice that, since j is even, $\pi (x_{j}) < \pi (r_{j})$, $\pi (r_j) < \pi (r_{j-1})$, and $\pi (r_{j-1})<\pi (x_{j-1})$ for all $x\in L$ due to the topological order of the vertices. By the assumption in the lemma, all blue edges $(x_j,x_{j-1})$ nest around $r_j$ and $r_{j-1}$. Therefore, any pair of such edges must be nested or they would cross. Hence, if $\pi (b_{j}) > \pi (a_{j})$, then $\pi (b_{j-1})<\pi (a_{j-1})$ or the blue edges $(b_j, b_{j-1})$ and $(a_j, a_{j-1})$ would cross (see Fig. 6 for example). Therefore, the order of the $(j-1)$-th copy of element vertices is the reverse order of the j-th copy. The same argument holds for $x_j$ and $x_{j+1}$ for all $x \in L$. Given that the order of the $(j-1)$-th and the order of the $(j+1)$-th copy of the element vertices are in reverse order of the j-th copy, the order of the $(j-1)$-th and $(j+1)$-th copies of the element vertices must be the same.     $\square$

The next corollary immediately follows from Lemma 3.

Corollary 1

If $\pi (r_{j}) < \min \{\pi (r_{j-1}), \pi (r_{j+1})\}$ for all even $j \in \{2, \dots , 2m-2\}$, then all element vertices with even subscript, $j \in \{2, \dots , 2m-2\}$ appear in the same order and all element vertices with odd subscript, $i \in \{1, \dots , 2m-1\}$ appear in the same order. Furthermore, all element vertices with even subscript, j, appear in the reverse order of all element vertices with odd subscript, i.

3.2 Final Reduction

We create n ordered triple gadgets as defined in Definition 2 and $2m-1$ order preserving gadgets as defined in Definition 3, connecting via the following set of edges:

• 1. $(a'_i, a''_i), (b'_i, b''_i), (c_i, c''_i) \in \mathtt {Red}$ for all odd $i \in [1, 2m-1]$.

• 2. $(r_j, l_{j-1}), (r_j, l_{j+1}) \in \mathtt {Red}$ for all even $j \in [1, 2m-1]$.

• 3. $(s, x^p_n) \in \mathtt {Blue}$ for all $p \in [1, n]$.

• 4. $(x^p_j, x^p_{j-1}) \in \mathtt {Blue}$ for all $p \in [1, n]$ and even $j \in [1, 2m-1]$.

• 5. $(x^p_j, x^p_{j+1}) \in \mathtt {Green}$ for all $p \in [1, n]$ and even $j \in [1, 2m-1]$.

• 6. $(h_i, r_i) \in \mathtt {Red}$ for all odd $i \in [1, 2m-1]$.

• 7. $(x^p_j, r_j) \in \mathtt {Red}$ for all $p \in [1, n]$ and even $j \in [1, 2m-1]$.

• 8. $(r_{2m-2}, s), (s, l_{2m-1}) \in \mathtt {Blue}$.

• 9. $(r_{2m-2}, l_{2m-1}) \in \mathtt {Red}$.

We connect the ordered triple and order preserving gadgets as described above, obtaining an instance (G, P) of UPBE- k. Using this reduction, we prove that UPBE-k is NP-complete for $k \ge 3$.

Theorem 1

UPBE- k is NP-complete for $k \ge 3$.

The proof follows from Lemmas 1, 2, and 3 and the constructions of the gadgets; please refer to our full paper for the proof [ADHL17].

4 UMPBE

In this section, we discuss the Upward Matching-Partitioned Book Embedding problem, where given an instance (G, P), each set of the partition P induces a subgraph in G that is a matching (i.e. no vertex is incident to more than one edge of each set of the partition). We first show UMPBE-4 is NP-complete and then show that UMPBE-2 is solved in O(n) time. When $|P|=1$, the algorithm in [HP99] for UPBE-1 can also solve UMPBE-1 in O(n) time.

4.1 UMPBE-4

Theorem 2

UMPBE-k is NP-complete for $k\ge 4$.

Proof

As with UPBE, it is clear that UMPBE is in NP since an order $\pi$ of vertices of G serves as a certificate. We show NP-hardness by reducing from Betweenness, adapting the proof of Theorem 1 to UMPBE-4. We again refer to the partitions in $P=\{\texttt {Red}, \texttt {Blue},\texttt {Green},\texttt {Yellow}\}$ as colors. The gadgets adapted from Sect. 3.1 are shown in Fig. 3.

Fig. 3.

Gadgets for the reduction to UMPBE-4. (Color figure online)

For odd i in $\{1,\ldots ,2m-1\}$ we connect gadgets with yellow edges $(h_i, r_i)$ and $(r_{i-1},l_i)$ (if $i>1$), and with the red edge $(r_{i+1},l_i)$ (if $i<2m-1$). Lemmas 1 holds for the new gadget replacing $x_i''$ by $x_i$. We omit its proof due to the similarity. The dashed arrows in Fig. 3 represent paths of alternating colors as described in the next paragraph. Lemma 3 also trivially holds. Therefore, given a valid order $\pi$ of vertices of G, the order of element vertices corresponds to a solution $\phi$ of the Betweenness instance.

It remains to show that, given a solution $\phi$ of the Betweenness instance, we can obtain a solution $\pi$ for the produced instance. The order in which the gadgets are embedded are the same as in the proof of Theorem 1 and, therefore, no edge between gadgets cross. We now show that each gadget has a cross-free embedding using $\phi$. The embedding of the ordered triple gadget is very similar to that shown in Fig. 2 and we chose $\pi (\alpha _i)>\pi (\omega _{i})$ or $\pi (\alpha _i)<\pi (\omega _{i})$ depending on whether a appears before c or vice-versa in $\phi$. In the order preserving gadget, we use the same order (resp., reverse order) of $\phi$ for even (resp., odd) j.

Fig. 4.

Embedding the order preserving gadget in Fig. 3 (center). (Color figure online)

Notice that the order preserving gadget now contains a binary tree and we cannot chose arbitrarily the order of vertices $x_j^*$ for $x\in L$. We call this tree the binary order preversing tree that ensures that $\pi (x_i) > \pi (r_i)$ and $\pi (x_j) < \pi (r_j)$ for all $x \in L$ for odd i and even j. The tree is obtained by ordering the vertices $x_j^*$ arbitrarily and building a binary tree that alternates between green/blue and yellow/red edges in order for the induced subgraph of each color to be a matching. The paths connecting $x_j^*$ to $x_j$ allows us to order the element vertices $x_j$ using $\phi$, independent of the order of vertices $x_j^*$. We construct such paths in the following way. Each of the paths contains n edges. These paths alternate between green/blue and yellow/red edges starting with the opposite color group from the last row of the tree. Let $x_j^*$ be the t-th vertex, $t\in \{1,\ldots ,n-1\}$, in an arbitrary order chosen as the order of the leaves of the order preserving tree. The colors of edges alternate between blue and red except for the t-th edge of the t-th vertex, such that the edge is green (resp., yellow) if the alternation would make it blue (resp., red). The embedding of the paths can be obtained by changing the order of the paths in an insertion sort manner, considering the last path (the path from $d_j^*$ to $d_j$ in Fig. 4) as the first element in the array and adding paths one by one in increasing order (see Fig. 4). Let $x_j^{t}$ be the t-th vertex of the path from $x_j^*$ to $x_j$ and let $y_j^t$ be the t-th vertex, $t\in \{1,\ldots ,n-1\}$, in the order chosen as the order of the leaves of the order preserving tree. Assume that the set A of all $x_j^{t-1}$ is embedded so that the vertices are contiguous in the spine. We embed the set B of vertices of the form $x_j^{t}$ immediately after the vertices in A in the reverse order in which they appear in A, apart from $y_j^{t}$. This order guarantees that no crossing is induced since all edges of the same color $(x_j^{t-1}, x_j^{t})$ are nested in parallel from A except for $(y_j^{t-1}, y_j^{t})$ which is of a different color. We can thus add $y_j^{t}$ in any place in the ordering of B.     $\square$

4.2 UMPBE-2

Theorem 3

Given an instance $(G,\{E_1,E_2\})$ where $G=(V,E)$, $E=E_1 \dot{\cup } E_2$ and both $(V,E_1)$ and $(V,E_2)$ are matchings, UMPBE can be solved in O(n) time where $n=|V|$.

Proof

In positive instances, $G = (V, E)$ must be 2-page book embeddable and therefore planar [BK79]. Hence $|E|=O(n)$. Every connected component of the undirected version of G must be either a path or a cycle, or else the induced subgraph of the partitions would not be a matching. Furthermore, the edges connected in such paths or cycles must alternate in color. Each connected component can be solved separately since the concatenation of the solution (total order on vertices) of connected components is a solution of the original problem. Without loss of generality, we consider only the case when G is connected.

We provide a reduction to 1D origami when G is a path and a reduction to single vertex flat foldability if G is a cycle. The reduction runs in O(n) time producing an instance with $n-1$ creases. Both the flat foldability of 1D origami and single vertex flat foldability can be determined in linear time [ABD+04, BH96]. A face in an 1D origami is defined as a segment in the 1D origami and a crease is defined as a place where the origami can be folded. A face in a single vertex crease pattern is the space between creases. A 1D origami is defined by a line while a single vertex crease pattern is defined by a single vertex where rays originating from the vertex represent creases.

For both the case of the path and the cycle, we create an instance of 1D origami and single vertex flat foldability, respectively, in the following way. For each edge $e\in E$ we create a mountain crease if $e \in \mathtt {Red}$ and a valley crease if $e \in \mathtt {Blue}$. Each face of the produced instance represents a vertex in G. The reduction will thus produce an instance where each face of the origami has the same length, which can be viewed as a linkage formed by identical bars. If G is a path (resp., cycle), the output will be a list (resp., circular list) containing the assignment of the creases on a line segment (resp., a single vertex origami). Start with one endpoint of the path or with an arbitrary vertex of the cycle. Traverse the undirected version of G using BFS. For each edge traversed add mountain (resp., valley) to the end of the list if the traversed edge corresponds to an edge in $E_1$ with the same direction of the traversal or to an edge in $E_2$ in the opposite direction (resp., corresponds to an edge in $E_2$ with the same direction of the traversal or to an edge in $E_1$ in the opposite direction). Since every edge is traversed once, the size of the list is $n-1$ (resp., n if a cycle). Thus, the only difference between single vertex crease patterns and 1D origami is that the faces form a cycle as opposed to a line segment, respectively.

Fig. 5.

A 1D origami crease pattern is shown (left) with mountain/valley labeled as M/V respectively, together with its folded state (center) and the corresponding UMPBE-2 instance (right). (Color figure online)

Fig. 6.

Example of a full construction of a reduction. Here, the instance of Betweenness is (L, C) where $L=\left\{ a, b, c, d\right\}$ and $C=\left\{ \langle a, b, c\rangle , \langle b, c, d\rangle , \langle d, b, a\rangle \right\}$. (Color figure online)

Due to the similarity of the reduction models for paths and cycles, it suffices to show the equivalence between instances when G is a path. As previously stated, each face of the paper corresponds to a vertex in G. Each crease represents an edge in G and whether the crease is a mountain fold or a valley fold in the final state of the origami determines the partition of the edges of G into Red or Blue edges. If we consider the starting vertex as the leftmost face of the unfolded paper and that $f_1$ is not flipped in the folded state, a mountain fold puts the adjacent face $f_2$ below $f_1$. Without loss of generality, the edge in G that represents the connection between $f_1$ and $f_2$ is in $E_2$ and points from $f_2$ to $f_1$. By repeating the argument for every edge, we conclude that G represents the above/below relation of faces of the folded state of the 1D origami and $E_1$ (resp., $E_2$) represents the creases that lie right (resp., left) of the folded state (see Fig. 5). Then, it is easy to verify that the origami is flat-foldable iff $(G,\{E_1,E_2\})$ is a positive instance of UMPBE.     $\square$