The Page Number of Monotone Directed Acyclic Outerplanar Graphs Is Four or Five

Follows directly from Property 1 of the canonical construction sequence. $◀$ Using Property 6, we next prove that no two sibling edges with the same parent cross in $\prec$.

Assume to the contrary that they cross; see Figure 4(b). We distinguish cases based on the relative order of the endpoints of these edges with respect to the common parent $v_p$. Let us first consider the case where the endpoints of at least one of the two edges either both precede $v_p$ or follow $v_p$. W.l.o.g. assume $v_p$ follows both $v_i$ and $v_{i+1}$ in $\prec$. By L.3, we have $v_{i+1}\prec v_i\prec v_p$. Since both $v_j$ and $v_{j+1}$ are children of $v_p$ and $j\ne i$, neither of them can be between $v_i$ and $v_{i+1}$ in $\prec$. Therefore, $\{v_i,v_{i+1}\}$ and $\{v_j,v_{j+1}\}$ cannot cross. We conclude that in order for $\{v_i,v_{i+1}\}$ and $\{v_j,v_{j+1}\}$ to cross, the endpoints of each of these two edges have to be on different sides of $v_p$ in $\prec$, that is, $v_p$ is between the endpoints of each of these edges in $\prec$. Since $\{v_i,v_{i+1}\}$ and $\{v_j,v_{j+1}\}$ cross, they are independent and therefore $i+1\ne j$. Assume w.l.o.g. that . In the following, we focus on the case where $v_i\prec v_p\prec v_{i+1}$; the case in which $v_{i+1}\prec v_p\prec v_i$ is symmetric. From L.3 we get that for every child $v_k$ of $v_p$ with $v_i\prec v_k\prec v_{i+1}$, we have . For $\{v_i,v_{i+1}\}$ and $\{v_j,v_{j+1}\}$ to cross either $v_j$ or $v_{j+1}$ has to be between $v_i$ and $v_{i+1}$ in $\prec$ contradicting that . $◀$

So far we have shown that tree edges can fit together in a single page and that the same holds for sibling edges having the same parent. Two questions that arise at this point are how to handle sibling edges with different parents and non-tree edges that are not sibling edges. For the latter, the idea is to assign these edges to groups such that each group has a designated sibling edge as representative. As we will see, a crossing between two non-tree edges of different groups can be reduced to a crossing between the groups’ representatives.

Let us formally introduced the concept of groups. As already mentioned, each group of non-tree edges has exactly one representative, which is a sibling edge. In other words, groups and sibling edges are in a one-to-one correspondence. Further, a sibling edge belongs to the group it represents. By Property 6, we denote with $N_i\subset N$ the group that is represented by the sibling edge $\{v_i,v_{i+1}\}$. It follows that $\{v_i,v_{i+1}\}\in N_i$. Note that the index $i$ stems from the rank of $v_i$ and $v_{i+1}$ in the canonical construction sequence $\pi$. Since not every pair of consecutive vertices in $\pi$ yields a sibling edge, it follows that there does not exist a group $N_i$ for every integer $i$ in $[1,n-1]$. We further require that the groups form a partition of $N$.

We now describe how to obtain such a partition of $N$. We do so by using the canonical construction sequence and by imposing further invariant properties that will help us later to show that no more than four colors are needed in order to color the groups that we will form. With this in mind, we also need to ensure that non-tree edges of the same group can always be assigned to the same page. We capture these properties with the following invariants.

Assume that all non-tree edges of $G_i$ with have been partitioned to groups $N_1,\mathrm{\dots },N_{i-1}$, such that the following hold for each non-empty group $N_k$ with $k\in [1,i-1]$:

1. N.1

   $N_k$ has exactly one representative sibling edge $\{v_k,v_{k+1}\}$ of $G_i$.

2. N.2

   For every edge $(u,v)$ of $G_i$ that belongs to group $N_k$ one of the following holds:

   1. (a)

      If $(v_k,v_{k+1})$ is the representative of $N_k$, then there is a directed path in $T(v_k)$ from $u$ to $v_k$ and a directed path in $T(v_{k+1})$ from $v_{k+1}$ to $v$.

   2. (b)

      If $(v_{k+1},v_k)$ is the representative of $N_k$, then there is a directed path in $T(v_{k+1})$ from $u$ to $v_{k+1}$ and a directed path in $T(v_k)$ from $v_k$ to $v$.

   Each vertex of these directed paths is incident to at least one edge of $N_k$.

3. N.3

   Each non-empty group $N_k$ is also associated with an outermost edge $(u,v)$, which is the solely edge on the outer face of $G_i$ among the edges of $N_k$ and covers all edges of $N_k$ in $\prec$, that is, for each $(u^{\prime },v^{\prime })\in N_k$, we have $u⪯u^{\prime }⪯v^{\prime }⪯v$.

We prove that the aforementioned invariants hold also for the non-tree edges of $G_{i+1}$ using the following approach. Consider vertex $v_{i+1}$. We distinguish cases based on whether the edge between the neighbors of $v_{i+1}$ in $G_i$ belongs to $T$ or to $N$.

We first consider the case in which the edge between the neighbors of $v_{i+1}$ in $G_i$ belongs to $T$. Let $v_p$ and $v_c$ be these neighbors, such that $v_p$ is the parent of $v_c$ in $T$. In this case, vertex $v_{i+1}$ is a child of $v_p$ in $G_{i+1}$, that is, the edge between $v_{i+1}$ and $v_p$ belongs to $T$, while the edge between $v_{i+1}$ and $v_c$ belongs to $N$. In particular, the edge between $v_{i+1}$ and $v_c$ is a sibling edge. We assign it to a new group $N_i$ and we make it both the representative and the outermost of this group. In other words, in this case we are creating a new group that solely consists of a single sibling edge. N.1–N.3 are satisfied because the edge between $v_{i+1}$ and $v_c$ cannot be associated with any of the groups $N_k$ with $k\in [1,i-1]$, belongs to the outer face of $G_{i+1}$ and trivially covers all edges of $N_i$, as there are no other edges in this group.

Consider now the case where the edge between the neighbors of $v_{i+1}$ in $G_i$ belongs to $N$. Let $v_l$ and $v_r$ be these neighbors. To simplify the presentation, we assume that the edge between $v_l$ and $v_r$ is oriented from $v_l$ to $v_r$; the other case is symmetric. Since $(v_l,v_r)$ belongs to $G_i$, by N.1 the edge $(v_l,v_r)$ has been assigned to a group, say $N_j$ with $j\in [1,i-1]$, whose representative edge is $(v_j,v_{j+1})$ by N.2. Assume that the edges connecting $v_{i+1}$ with $v_l$ and $v_r$ in $G_{i+1}$ are outgoing from $v_{i+1}$; the case in which the edges connecting $v_{i+1}$ with $v_l$ and $v_r$ in $G_{i+1}$ are incoming to $v_{i+1}$ is symmetric. Under this assumption, the edge $(v_{i+1},v_r)$ is the non-tree edge incident to $v_{i+1}$ in $G_{i+1}$. We proceed by assigning this edge to $N_j$. Regarding N.1 there is nothing to be proven, as $N_j$ is an existing group. Since $(v_j,v_{j+1})$ is the representative of $N_j$, we know that by N.2 applied on $G_i$ that there exist a directed path in $T(v_j)$ from $v_l$ to $v_j$ and a directed path in $T(v_{j+1})$ from $v_{j+1}$ to $v_r$. Since $v_{i+1}$ has an outgoing edge to $v_l$, it follows that there is a directed path from $v_{i+1}$ to $v_l$, as well, guaranteed that N.2 is satisfied from $G_{i+1}$. To prove that N.3 is satisfied in $G_{i+1}$, we first observe that $(v_l,v_r)$ is the outermost edge of $N_j$, since it is the one incident to the outer face of $G_i$ among the edges of $N_j$ by N.2. As a result, it covers all edges of $G_i$ belonging $N_j$ in $\prec$. In $G_{i+1}$, the edge $(v_{i+1},v_r)$ becomes that outermost edge of $N_j$, as it is the solely edge of $N_j$ incident to the outer face of $G_{i+1}$. Furthermore, $(v_{i+1},v_r)$ covers all edges of $G_{i+1}$ belonging $N_j$ in $\prec$, since $v_{i+1}$ appear right before $v_l$ in $\prec$. This guarantees that N.3 is satisfied in $G_{i+1}$.

Assume that no two (non-tree) edges of the same group cross in $\prec$ for the subgraph $G_i$ of $G$. By Invariant N.3, it follows that the non-tree edge incident to $v_{i+1}$ in $G_{i+1}$ covers all edges of the same group in $G_i$, as it becomes the outermost of this group. This implies that no two edges of the same group cross in $\prec$ for the subgraph $G_{i+1}$ of $G$. This completes the proof, since in $G_2$ the property trivially holds. $◀$

Let $(u,v)$ and $(x,y)$ be two edges of $N_i$ and $N_j$, respectively. Let also $\{v_i,v_{i+1}\}$ and $\{v_j,v_{j+1}\}$ be the representative sibling edges of $N_i$ and $N_j$, respectively. We assume that the former edge is oriented from $v_i$ to $v_{i+1}$, while the latter from $v_j$ to $v_{j+1}$; the remaining cases are handled symmetrically. It follows by N.2 that $u\in T(v_i)$, $v\in T(v_{i+1})$, $x\in T(v_j)$ and $y\in T(v_{j+1})$. Since $v_k$ and $v_l$ are the group parents of $N_i$ and $N_j$, these relationships imply that $u,v\in T(v_k)$ and $x,y\in T(v_l)$. Assume to the contrary that $(u,v)$ and $(x,y)$ cross in $\prec$. Consider first the case where the two subtrees $T(v_k)$ and $T(v_l)$ are vertex-disjoint. L.2 implies that both $u$ and $v$ either precede or follow both $x$ and $y$ in $\prec$. This implies that $(u,v)$ and $(x,y)$ do not cross in $\prec$; a contradiction. Hence, $T(v_k)$ and $T(v_l)$ are not vertex-disjoint.

Assume first that $T(v_k)$ and $T(v_l)$ share the same root, that is, $v_k=v_l$; see Figure 6(a). It follows by the assumptions of the lemma that the representative sibling edges $(v_i,v_{i+1})$ and $(v_j,v_{j+1})$ of $N_i$ and $N_j$ are independent, implying that the subtrees $T(v_i)$, $T(v_{i+1})$, $T(v_j)$ and $T(v_{j+1})$ are vertex-disjoint. By N.2, we know that the vertices of each of these four subtrees are consecutive in $\prec$. Since $(u,v)$ and $(x,y)$ cross in $\prec$, it follows that either $u\prec x\prec v\prec y$ or $x\prec u\prec y\prec v$. W.l.o.g. consider the former case; the latter follows by the same argument. Since $u\in T(v_i)$, $v\in T(v_{i+1})$, $x\in T(v_j)$ and $y\in T(v_{j+1})$ and since the vertices of each of these four subtrees are consecutive in $\prec$, it follows that $v_i\prec v_j\prec v_{i+1}\prec v_{j+1}$, that is, the representative edges of $N_i$ and $N_j$ cross in $\prec$; a contradiction to Property 7.

Hence, we deduce that $v_k\ne v_l$. Since $T(v_k)$ and $T(v_l)$ are not vertex-disjoint and since $v_k\ne v_l$, it follows that either $T(v_k)$ is a proper subtree of $T(v_l)$ or vice versa. Assume the former, that is, $T(v_k)⊊T(v_l)$; see Figure 6(b). Since the vertices of $T(v_k)$ appear consecutively in $\prec$, it follows that in order for $(u,v)$ and $(x,y)$ to cross in $\prec$, one endpoint of $(x,y)$, say w.l.o.g. $x$, has to be contained in $T(v_k)$. Then, by N.2, there exists a path between $x$ and $v_l$ in $T$, such that with the exception of $v_l$ all vertices on this path are incident to an edge of $N_j$. Since $x$ belongs also to $T(v_k)$, this path necessarily contains vertex $v_k$, which is a contradiction to the fact that $v_k$ is not an endpoint of an edge in $N_j$. $◀$

Our proof is by induction on the length of canonical construction sequence. Assume that we have computed a $4$-coloring of the non-tree edges of $G_i$ satisfying the next invariants:

1. C.1

   Edges of the same group in $G_i$ are of the same color.

2. C.2

   Each vertex in $G_i$ is incident to at most two edges belonging to groups of different colors, that is, the non-tree edges incident to it are either single-colored or bicolored.

3. C.3

   For every tree edge $\{v_p,v_c\}$ on the outer face of $G_i$, with $v_c$ being a child of $v_p$, all non-tree edges incident to $v_c$ belong to the same group, that is, they are single-colored.

4. C.4

   If $N_k$ and $N_l$ are two distinct groups with group parents $v_p$ and $v_q$, such that either $v_p$ is an endpoint of an edge in $N_l$ or $v_q$ is an endpoint of an edge in $N_k$, then $N_k$ and $N_l$ are of different colors.

5. C.5

   If $N_k$ and $N_l$ are two distinct groups with common group parent $v_p$, such that their representative sibling edges $\{v_k,v_{k+1}\}$ and $\{v_l,v_{l+1}\}$ share an endpoint, then $N_k$ and $N_l$ are of different colors.

Clearly, for $G_2$ all invariants are satisfied since $N=\mathrm{\varnothing }$. So, we assume that $i>2$ and we will prove that we can appropriately color the edges incident to $v_{i+1}$ in $G_{i+1}$, such that C.1–C.5 are satisfied by for the non-tree edges in $G_{i+1}$. We distinguish cases based on whether the edge between the neighbors of $v_{i+1}$ in $G_i$ belongs to $T$ or to $N$, that is, $v_{i+1}$ is stacked on a tree or a non-tree edge of $G_i$, respectively.

Assume first that the edge, say $(v_l,v_r)$, between the neighbors $v_l$ and $v_r$ of $v_{i+1}$ in $G_i$ belongs to some group $N_j$; see Figure 7(a). By C.1, we can assume that the color assigned to the edges of $N_j$ is w.l.o.g. $c_1$. To simplify the presentation, we assume that the two edges incident to $v_{i+1}$ in $G_{i+1}$ are outgoing from $v_{i+1}$, that is, $(v_{i+1},v_l)$ and $(v_{i+1},v_l)$ belong to $G$; the case of these edges being incoming is symmetric by exchanging the roles of $v_l$ and $v_r$. Under this assumption, the non-tree edge incident to $v_{i+1}$ in $G_{i+1}$ is the edge $(v_{i+1},v_r)$; the edge $(v_{i+1},v_r)$ is the tree edge incident to $v_{i+1}$ in $G_{i+1}$. Since $(v_{i+1},v_r)$ belongs to $N_j$, we color it with color $c_1$, so as to guarantee C.1. Since the set of colors that is used for the edges incident to $v_r$ and $v_l$ does not change and since there is only one non-tree edge incident to $v_{i+1}$ in $G_{i+1}$ (namely, the edge $(v_{i+1},v_r)$), it follows that C.2 is guaranteed in $G_{i+1}$. Regarding C.3, we observe that the tree edge $(v_{i+1},v_r)$ incident to $v_{i+1}$ in $G_{i+1}$ is an edge on the outer face of $G_{i+1}$. Since for the tree edge $(v_{i+1},v_r)$ $v_{i+1}$ is the child of $v_l$ in $T$ and since there is only one non-tree edge incident to $v_{i+1}$ in $G_{i+1}$ (namely, the edge $(v_{i+1},v_r)$), it follows that C.3 is maintained in $G_{i+1}$. Since $v_{i+1}$ is a leaf in the restriction of $T$ to $G_{i+1}$, C.4 is satisfied by the inductive hypothesis. By the same argument and the fact that no new sibling edges are introduced in $G_{i+1}$, C.5 holds in $G_{i+1}$. This completes the case where the edge between the neighbors of $v_{i+1}$ in $G_i$ belongs $N$.

We proceed to the more tedious case, where the edge between the neighbors of $v_{i+1}$ in $G_i$ belongs to $T$; see Figure 7(b). Let $v_p$ and $v_c$ be the endpoints of this edge, such that $v_p$ is the parent of $v_c$ in $T$. By Property 1, $c=i$ holds. Also, by T.3, it follows that $v_c=v_i$ is a leaf in the restriction of $T$ to $G_i$. In this case, the edge $\{v_i,v_{i+1}\}$ is the representative of the new group $N_i$ in $G_{i+1}$ solely consisting of $\{v_i,v_{i+1}\}$, while $\{v_p,v_{i+1}\}$ belongs to $T$. The former implies that regardless of the color that we will assign to $N_i$, C.1 holds in $G_{i+1}$. We further observe that since $v_i$ and $v_{i+1}$ are siblings and $v_i$ is a leaf in the restriction of $T$ to $G_i$, it remains a leaf also in the restriction of $T$ to $G_{i+1}$. In particular, this implies that $v_i$ is not the group parent of some group in $G_{i+1}$.

To guarantee C.4 and C.5, we have to choose the color for the representative sibling edge $\{v_i,v_{i+1}\}$ in $N_i$ appropriately. In particular, we have to ensure that the color chosen is different from the colors incident to $v_p$ and $v_i$ in $G_i$. By C.2, the non-tree edges incident to $v_p$ in $G_i$ have at most two colors, say $c_1$ and $c_2$. Since $\{v_p,v_i\}$ is incident to the outer face of $G_i$ and since $v_i$ is a child of $v_p$ in $T$, by Item C.3 the non-tree edges incident to $v_i$ in $G_i$ belong to the same group; let $c_3$ be the color assigned to this group. The color that we assign to $N_i$ is one not belonging in $\{c_1,c_2,c_3\}$, say $c_4$.

Invariant C.2 is trivially satisfied at $v_{i+1}$ because of its degree in $G_{i+1}$. Since by C.3 the non-tree edges incident to $v_i$ in $G_i$ belong to a single group, C.2 is satisfied for $v_i$ in $G_{i+1}$. The same holds for $v_p$ by the inductive hypothesis, since the edge $\{v_p,v_{i+1}\}$ belongs to $T$. Hence, C.2 is maintained $G_{i+1}$. Since the edge $\{v_p,v_{i+1}\}$ belongs to the outer face of $G_{i+1}$ and since $v_{i+1}$ has only one non-tree edge incident to it in $G_{i+1}$ (i.e., the edge $\{v_i,v_{i+1}\}$), C.3 is maintained in $G_{i+1}$. Note that the edge $(v_p,v_i)$ is not on the outer face of $G_{i+1}$.

For C.4, consider a group $N_k$ with and group parent $v_q$ and assume that either $v_p$ is an endpoint of an edge in $N_k$ or $v_q$ is an endpoint of an edge in $N_i$. For the latter case, note that since $N_i$ consists only of its representative sibling edge $\{v_i,v_{i+1}\}$, the only possible candidate for $v_q$ is $v_i$. However, $v_i$ is a leaf in $G_{i+1}$ and therefore not a parent of a group. For the former case, that is, there is a non-tree edge incident to $v_p$ (the parent of $N_i$) having the same color as $N_i$, we argue with our definition of $c_4$ that this is not the case. For C.5 it is sufficient to consider a possible sibling edge sharing an endpoint with $\{v_i,v_{i+1}\}$. The only possible candidate in $G_{i+1}$ would be a sibling edge $\{v_{i-1},v_i\}$. However, we ensure that $c_4$ is different from the color of any other non-tree edge incident to $v_i$ which is sufficient to maintain C.5 in $G_{i+1}$. This completes the proof that C.1–C.5 are maintained in $G_{i+1}$.

To prove that no two non-tree edges assigned to two groups of the same color cross in $\prec$, we combine all properties that we have obtained so far. Let $e$ and $e^{\prime }$ be two such edges and assume that $e$ and $e^{\prime }$ belong to $N_i$ and $N_j$ and that $v_p$ and $v_q$ are the group parents of $N_i$ and $N_j$, respectively. By C.1 and Property 8, it follows that if $N_i=N_j$, then $e$ and $e^{\prime }$ do not cross in $\prec$, as desired. Hence, we may assume that $N_i$ and $N_j$ are two distinct groups. If $v_p$ is an endpoint of an edge in $N_i$ or $v_q$ is an endpoint of an edge in $N_j$, then $N_i$ and $N_j$ are of different colors by C.4; a contradiction to the fact that $e$ and $e^{\prime }$ belong to groups of the same color. It follows that neither $v_p$ is an endpoint of an edge in $N_i$ nor $v_q$ is an endpoint of an edge in $N_j$. In this case, if $v_p\ne v_q$, then by Property 9, $e$ and $e^{\prime }$ do not cross in $\prec$. Therefore, we may assume that $N_i$ and $N_j$ share the same parent, that is, $v_p=v_q$. If the representative sibling edges of $N_i$ and $N_j$ share an endpoint, then by C.5, it follows that $N_i$ and $N_j$ are of different colors; a contradiction. Hence, the representative sibling edges of $N_i$ and $N_j$ are independent. Then, again Property 9 applies which states that $e$ and $e^{\prime }$ do not cross in $\prec$. This concludes the proof of the property, which in turn coupled with Property 5 concludes the proof of the upper bound of Theorem 2. $◀$