\section{Introduction}\label{se:intro} 
\begin{figure}[b!]
\centering
\subfloat[\label{fig:l-drawing-example}]{\includegraphics[page=1,height=0.2\textwidth]{octahedron}}\hfil
\subfloat[\label{fig:nodetrix-example}]{\includegraphics[height=0.2\textwidth,page=1]{nt-representation}}\hfil
\subfloat[\label{fig:clique-example}]{\includegraphics[page=1,height=0.2\textwidth]{clique-planarity}}
\caption{
(a) A planar L-drawing, which determines a $4$-modal embedding. (b) A planar NodeTrix representation. (c) A planar intersection-link representation using comb-shaped polygons.
}
\end{figure}
Computing $k$-modal embeddings of planar digraphs, for some positive even integer $k$ called \emph{modality}, is an important algorithmic task at the basis of several types of graph visualizations. 
In \emph{$2$-modal embeddings}, also called \emph{bimodal embeddings}, the outgoing and the incoming edges at each vertex form two disjoint sequences. 
Bimodal embeddings are ubiquitous in Graph Drawing. 
For instance, level planar drawings~\cite{BattistaN88,JungerLM98} and upward-planar drawings~\cite{BattistaT87,GargTamassia01}---two of the most deeply-studied graph drawing standards---determine bimodal embeddings. 
\emph{4-modal embeddings}, where the outgoing and the incoming edges at each vertex form up to four disjoint sequences with alternating orientations, arise in the context of planar \mbox{L-drawings} of digraphs. In an \emph{L-drawing} of an $n$-vertex digraph, introduced by Angelini {\em et al.}\xspace~\cite{AngeliniLBDPRT16}, vertices are placed on the $n \times n$~grid so that each vertex is assigned a unique $x$-coordinate and a unique $y$-coordinate and each edge $uv$ (directed from $u$ to $v$) is represented as a $1$-bend orthogonal polyline composed of a vertical segment incident to $u$ and of a horizontal segment incident to $v$.  
Recently, Chaplick {\em et al.}\xspace~\cite{ccdnptw-plddg-17} addressed the question of deciding the existence of \emph{planar L-drawings}, i.e., L-drawings whose edges might possibly overlap but do not cross and observe that the existence of a $4$-modal embedding is a necessary condition for a digraph to admit such a representation (\cref{fig:l-drawing-example}).


To the best of our knowledge, no further relationships have been explicitly pointed out in the literature between modal embeddings and notable drawing models for modality values greater than four, yet they do exist.
\mbox{Da Lozzo} {\em et al.}\xspace~\cite{LozzoBFP18} and Di Giacomo {\em et al.}\xspace~\cite{GiacomoLPT17} study the planarity of \emph{NodeTrix representations} of flat clustered networks, a hybrid representational model introduced by Henry, Fekete, and McGuffin~\cite{DBLP:journals/tvcg/HenryFM07}, where clusters and intra-cluster edges are represented as adjacency-matrices, with rows and columns for the vertices of each cluster, and inter-cluster edges are Jordan arcs connecting different matrices (\cref{fig:nodetrix-example}).
For clusters containing only two vertices, it is possible to show that the problem of computing planar NodeTrix representations coincides with the one of testing whether a special digraph, called the \emph{canonical digraph\xspace}, associated to the network admits a $6$-modal embedding. 
For higher values of modality, $k$-modal embeddings occur in the context of Intersection-Link representations of flat clustered networks. In an \emph{intersection-link representation}~\cite{DBLP:journals/jgaa/AngeliniLBFPR17,DBLP:conf/gd/AngeliniEH0KLNT18}, vertices are represented as translates of the same polygon, intra-cluster edges are represented via intersections between the 
polygons corresponding to their endpoints, and inter-cluster edges---similarly to NodeTrix representations---are Jordan arcs connecting the polygons corresponding to their endpoints. For any modality $k\geq 2$, it can be shown that testing the existence of a $k$-modal embedding of the canonical digraph\xspace of a flat clustered network with clusters of size two is equivalent to testing the existence of an intersection-link representation in which the curves representing inter-cluster edges do not intersect, when vertices are drawn as comb-shaped polygons (\cref{fig:clique-example}).



{\bf Related Work.}
It is common knowledge that the existence of bimodal embeddings can be tested in linear time: Split each vertex $v$ that has both incoming and outgoing edges into two vertices $v_{in}$ and $v_{out}$, assign the incoming edges~to~$v_{in}$ and the outgoing edges to $v_{out}$,
connect $v_{in}$ and $v_{out}$ with an edge, and test the resulting (undirected) graph \mbox{for planarity using any of} the linear-time planarity-testing algorithms~\cite{BoothL76,HopcroftT74}. 
Despite this, most of the planarity variants requiring bimodality are NP-complete; for instance, upward planarity~\cite{GargTamassia01}, windrose planarity~\cite{AngeliniLBDKRR16}, {partial-level planarity}~\cite{BrucknerR17},
clustered-level planarity and $T$-level planarity~\cite{Angelini15,KlemzR17}, ordered-level planarity and bi-monotonicity~\cite{KlemzR17}. In this scenario, a notable exception is represented by the classic level planarity problem, which can be solved in linear time~\cite{JungerLM98}, and its generalizations on the standing cylinder~\cite{BachmaierBF05}, rolling cylinder and the torus~\cite{AngeliniLBFPR16}. 
Although the existence of a bimodal embedding is easy to test,  Binucci, Didimo, and Giordano~\cite{BinucciDG08} prove that the related problem of finding the maximum bimodal subgraph of an embedded planar digraph is an NP-hard problem.
Moreover, Binucci, Didimo, and Patrignani~\cite{BinucciDP14} show that, given a \emph{mixed
planar graph}, i.e., a planar graph whose edge set is partitioned into a set of directed edges and a set of undirected edges, orienting the undirected edges in such a way that the whole graph admits a bimodal embedding is an NP-complete problem. 
On the other hand, the question regarding the computational complexity of constructing $k$-modal embedding for $k\geq 4$ has not been addressed, although the related problem of testing the existence of \mbox{planar L-drawings has been recently proved NP-complete~\cite{ccdnptw-plddg-17}.}
 

\paragraph{\bf Our results.}
We study the complexity of the \kmodality{k} problem, which asks for the existence of $k$-modal embeddings of planar digraphs---with an emphasis on $k=4$. \mbox{Our results are as follows:}
\begin{enumerate}[-]
	\item We demonstrate a complexity dichotomy for the \mbox{\sc $4$-Modality}\xspace problem with respect to the maximum degree $\Delta$ of the input digraph. Namely, we show NP-completeness when $\Delta \geq 7$
	\ifshortversion{{\mbox(see 
\section{Conclusions}\label{se:conclusions}

In this paper, we studied the complexity of the \kmodality{k} problem, with special emphasis on $k=4$. We provided complexity, algorithmic, and combinatorial results. 
Our main algorithmic contribution for $k=4$ and $\Delta \leq 6$ leverages an elegant connection with the {\sc NAE}\xspace-satisfiability of special CNF formulas, whose study allowed us to strengthen a result in~\cite{PorschenRS03}.
Moreover, we showed notable applications of the previous results to some new interesting embedding problems for clustered networks, some of which solve open problems \mbox{in this area~\cite{DBLP:journals/jgaa/AngeliniLBFPR17,GiacomoLPT17}}. 

\subsection{Simply-Connected Graphs}\label{se:simply}
We first observe that the \maxkmodality{k} problem is a generalization of the \kmodality{k}problem. In fact, a directed graph $G=(V,E)$ admits a $k$-modal embedding if and only if the pair $\langle G, m \rangle$, with $m(v)=k, \forall v \in V(G)$, is a positive instance of the \maxkmodality{k} problem.

\begin{observation}\label{obs:reduction}
\kmodality{k} reduces in linear time to \maxkmodality{k}.
\end{observation}

Let $\langle G, m: V(G) \rightarrow \even{4} \rangle$ be an instance of \mbox{\sc $4$-MaxModality}\xspace; also, let $\beta$ be a leaf-block of the BC-tree $\calT{}$ of $G$ and let $v$ be the parent cut-vertex of $\beta$ in $\calT{}$. We denote by $G^-_\beta$ the subgraph of $G$ induced by $v$ and the vertices of $G$ not in $\beta$, i.e., $G^-_\beta = G - (\beta - \{v\})$. Also, let $B(\calT{})$ be the set of blocks in $\calT{}$.
We show that \maxkmodality{k}  (and \kmodality{k}, by \cref{obs:reduction}) in simply-connected digraphs is Turing reducible to \maxkmodality{k} in biconnected digraphs. 

\begin{theorem}\label{th:simply-to-biconnected}
Given a subroutine {\sc TestBiconnected} that tests \maxkmodality{k} for \linebreak biconnected~instances, there exists a procedure  {\sc TestSimplyConnected} that tests \linebreak \maxkmodality{k} for simply-connected digraphs. Further, given an instance $\langle G, m \rangle$ of \linebreak \maxkmodality{k}, the runtime of {\sc TestSimplyConnected($\langle G, m \rangle$)} is
$$\mathcal{O}\big(|G|+ \log{k}\sum_{\beta \in B(\calT{})} r(\beta)\big),$$ where $r(\beta)$ is the runtime of  {\sc TestBiconnected($\langle \beta, m \rangle$)} and $\calT{}$ is the BC-tree of $G$. 
\end{theorem}

\begin{sketch}The algorithm selects a leaf-block $\beta$ of $\mathcal T$, with parent cut-vertex $v$, and finds an embedding of $\beta$ with the minimum modality at $v$ satisfying $m$ at all vertices, by performing a binary search using the {\sc TestBiconnected} procedure. We then remove $\beta$, replace $G$ with $G^-_\beta$, and update the value of $m(v)$, so to account for the alternations at $v$ introduced by $\beta$. The procedure terminates when all the blocks have been processed.
Therefore, since the total number of calls to subroutine {\sc TestBiconnected} is bounded by the number of blocks of $G$, which is ${O}(|\mathcal T|)={O}(|G|)$ multiplied by $\log{k}$, the overall running time is \mbox{${O}(|G|+ \log{k} \sum_{\beta \in B(\calT{})} r(\beta))$}.\end{sketch}




\subsection{Biconnected Graphs} \label{se:bico}

\ifshortversion{
To handle the decomposition of a biconnected digraph into its triconnected components, we use SPQR-trees, a data structure introduced by Di Battista and Tamassia~\cite{BattistaT90}. 

\paragraph{\bf SPQR-trees.} 
\begin{figure}[t]
\includegraphics[width=\textwidth]{flatSpqr}
\caption{
\ifshortversion{
(left) A $4$-modal embedding of a simply-connected planar digraph $G$. (right) The SPQR $\cal T$ of the block $\cal B$ of $G$ rooted at edge $e=uv$. The extended skeletons of all non-leaf nodes of $\cal T$ are shown; virtual edges corresponding to S-, P-, and R-nodes are thick. 
}\fi
}\label{fi:spqr}
\end{figure}
Let $G$ be a biconnected digraph. We consider SPQR-trees that are rooted at an edge $e$ of $G$, called the \emph{reference edge}. The rooted SPQR-tree $\cal T$ of $G$ with respect to $e$ describes a recursive decomposition of $G$ induced by its split pairs. The nodes of $\cal T$ are of four types: S, P, Q, and R. 
Each node $\mu$ of $\cal T$ has an associated undirected multigraph $\skel(\mu)$, called the \emph{skeleton} of $\mu$, with two special nodes $u_\mu$ and $v_\mu$ (the \emph{poles} of $\mu$), and an associated subgraph $\pert(\mu)$ of $G$, called \emph{pertinent} of $\mu$. The skeleton graph equipped with the edge $u_\mu v_\mu$, called the \emph{parent edge}, is the \emph{extended skeleton} of $\mu$. Refer to \red{ \cref{fi:spqr}(right)}. 
Each edge of $\skel(\mu)$, called \emph{virtual edge}, is associated with a child of $\mu$ in $\cal T$. The skeleton of $\mu$ describes how the pertinent graphs of the children of $\mu$ have to be ``merged'' via their poles to obtain $\pert(\mu)$. 
The extended skeleton of an S-, P-, R-, and Q-node is a cycle, parallel, triconnected graph, and a $2$-gon, respectively. It follows that skeleton and pertinent graphs are always biconnected once the parent edge is added. 
A \emph{series-parallel digraph} is a biconnected planar digraph whose SPQR-tree only contains S-, P-, and Q-nodes. A \emph{partial 2-tree} is a digraph whose every block is a series-parallel digraph.

A digraph $G$ is planar if and only if the skeleton of each R-node in the SPQR-tree of $G$ is planar.
By selecting \emph{regular embeddings} for the skeletons of the nodes of $\cal T$, that is, embeddings in which the parent edge is incident to the outer face, we can construct any embedding of $G$ with the edge $e$ on the outer face, where the choices for the embeddings of the skeletons are all and only the (i) flips of the R-nodes and the (ii) permutations of the P-nodes.
}\fi


\smallskip
Consider a pair $\langle G, m \rangle$ such that $G$ is biconnected and let $\cal E$ be a planar embedding of $G$. Also, let $\calT{}$ be the SPQR-tree of $G$ rooted at an edge $e$ of $G$ incident to the outer face of~$\cal E$.
We will assume that the virtual edges of the skeletons of the nodes in $\calT{}$ are oriented so that the extended skeleton of each node $\mu$ is a DAG with a single source $u_\mu$ and a single sink $v_\mu$.
 \ifshortversion{}\else{This implies that the virtual edges belonging to the extended skeleton of a P-node have the same orientation, from $u_\mu$ to $v_\mu$, and that the virtual edges of the skeleton of an S-node form a directed path from $u_\mu$ to $v_\mu$.} \fi
Let $\mu$ be a node of $\calT{}$ and let $\cal E_\mu$ be the planar (regular) embedding of $\skel(\mu)$ induced by $\cal E$. 
For an oriented edge $d=uv$ of $\skel(\mu)$, the \emph{left} and \emph{right face} of $d$ in $\cal E_\mu$ is the face of $\cal E_\mu$ seen to the left and to the right of $d$, respectively, when traversing this edges from~$u$ to $v$. We define the \emph{outer left (right) face} of $\cal E_\mu$ as the left (right) face of the edge $u_\mu v_\mu$ in $\cal E_\mu$.


\paragraph{\bf Embedding tuples.}
An \emph{embedding tuple} (for short, \emph{tuple}) is a $4$-tuple $\langle \sigma_1, a, \sigma_2, b\rangle$, where $\sigma_1,\sigma_2 \in \{\uparrow, \downarrow\}$ are orientations and $a,b \in \mathds{N}$ are non-negative integers. 
Consider two tuples $t=\langle \sigma_1, a, \sigma_2, b \rangle$ and $t'=\langle \sigma'_1, a', \sigma'_2, b' \rangle$. We say that $t$ \emph{dominates} $t'$, denoted as  $t \preceq t'$, if
$\sigma_1 = \sigma'_1$, $\sigma_2 = \sigma'_2$, $a \leq a'$, and $b \leq b'$. Also, we say that $t$ and $t'$ are \emph{incompatible}, if none of them dominates the other. 
Since the relationship $\preceq$ is reflexive, antisymmetric, and~transitive,~it~defines~a~poset~$(T, \preceq)$, where $T$ is the set of embedding tuples. 
A subset $S \subseteq T$ is \emph{succinct} or an \emph{antichain}, if the tuples in $S$ are pair-wise incompatible. 
Consider two subsets $S,S' \subseteq T$ of tuples. We say that $S$ \emph{dominates} $S'$, denoted as $S \preceq S'$, if for any tuples $t' \in S'$ there exists at least one tuple $t \in S$ such that $t \preceq t'$. Also, $S$ \emph{reduces} $S'$ if  $S \preceq S'$ and $S \subseteq S'$. Finally, $S$ is a \emph{gist} of $S'$, \mbox{if $S$ is succinct and reduces~$S'$.}

Let $e_u$ and $e_v$ be the edges of $\pert(\mu)$ incident to the outer left face of $\cal E_\mu$ and to $u_\mu$ and $v_\mu$, respectively, possibly $e_u = e_v$. Also, let $a$ and $b$ be non-negative integers.
We say that the embedding $\cal E_\mu$ \emph{realizes} tuple $\langle \sigma_1, a, \sigma_2, b\rangle$, if $\sigma_1 = \sigma(e_u, u_\mu)$, $\sigma_2 = \sigma(e_v, v_\mu)$, and $a$ and $b$ are the number of inner faces of $\cal E_\mu$ whose (two) edges incident to $u_\mu$ and to $v_\mu$, respectively, form an alternating pair.
A tuple $t=\langle \sigma_1, a, \sigma_2, b \rangle$ is \emph{realizable by} $\mu$, if there exists an embedding of $\pert(\mu)$ that realizes~$t$, and \emph{admissible}, if $a \leq m(u)$ and $b \leq m(v)$. 
A tuple is \emph{good for} $\mu$ if it is both admissible and realizable by $\mu$.
We denote by $S(\mu)$ the gist of the set of good tuples for a node $\mu$. Let $e_\mu$ be the virtual edge representing $\mu$ in the skeleton of the parent of $\mu$ in $\calT{}$, with a small overload of notation, we also denote $S(\mu)$ by $S(e_\mu)$.
For a tuple $t=\langle \sigma_1, a, \sigma_2, b \rangle \in S(e_\mu)$, where $e=u_\mu v_\mu$, the pair $(\sigma_1, a)$ is the \emph{embedding pair} of $t$ at $u_\mu$; likewise, the pair $(\sigma_2, b)$ is the \emph{embedding pair} of $t$ at $v_\mu$.
We have the following substitution lemma.

\begin{figure}[tb!]
\centering
    \subfloat
    {\includegraphics[page=2,scale=.9]{substitution}\label{fig:substitutionOrig}} \hfil
    \subfloat
    {\includegraphics[page=3,scale=.9]{substitution}\label{fig:substitutionSwap}} 
\caption{ Illustration for the proof of \cref{le:substitution}. The parity of $t$ and $t'$ is the same at $u_\mu$ and different at $v_\mu$; in particular, even if a new alternation is introduced between the pair $(e,e')$ at~$v_\mu$, the different parity guarantees that the modality at~$v_\mu$ does not increase from $\mathcal E$ to $\mathcal E'$.
}
\label{fig:substitution}
\end{figure}



\begin{lemma}\label{le:substitution}

Let $\cal E$ be a planar embedding of $G$ satisfying $m$.
Let $\mu$ be a node of $\calT{}$ and let $\cal E_\mu$ be the embedding of $\pert(\mu)$ induced by $\cal E$. Also, let $\cal E'_\mu \neq \cal E_\mu$ be an embedding of $\pert(\mu)$ satisfying~$m$. 
Then, $G$ admits an embedding $\cal E'$ satisfying $m$ in which the embedding of $\pert(\mu)$ 
is $\cal E'_\mu$, if $t' \preceq t$, where $t$ and $t'$ are the embedding tuples realized by ${\cal E_\mu}$ and by ${\cal E'_\mu}$, respectively.
\end{lemma}


\begin{sketch}
We show how to construct a drawing $\Gamma'_G$ of $G$ satisfying $m$ in which the embedding of $\pert(\mu)$ is $\mathcal E'_\mu$; see \cref{fig:substitution}. 
Let $\Gamma_G$ be a drawing of $G$ whose embedding is $\mathcal E$. Remove from $\Gamma_G$ the drawing of all the vertices of $\pert(\mu)$ different from $u_\mu$ and $v_\mu$ and the drawing of all the edges of $\pert(\mu)$. Denote by $f$ the face of the resulting embedded graph $G^-$ that used to contain the removed vertices and edges. We obtain $\Gamma'_G$ by inserting a drawing of $\pert(\mu)$ whose embedding is $\mathcal E'_\mu$ in the interior of $f$ so that vertices $u_\mu$ and $v_\mu$ are identified with their copies in $G^-$. 
We can prove that the embedding $\mathcal E'$ of $\Gamma'_G$ satisfies $m$ by exploiting 
the interplay between the parity and the number of alternations at $u_\mu$  (at $v_\mu$) in $t'$ and $t$ when $t' \preceq t$.
\end{sketch}


\begin{fullproof}
We show how to construct a drawing $\Gamma'_G$ of $G$ satisfying $m$ in which the embedding of $\pert(\mu)$ is $\mathcal E'_\mu$; see \cref{fig:substitution}. 
Let $\Gamma_G$ be a drawing of $G$ whose embedding is $\mathcal E$. Remove from $\Gamma_G$ the drawing of all the vertices of $\pert(\mu)$ different from $u_\mu$ and $v_\mu$ and the drawing of all the edges of $\pert(\mu)$. Denote by $f$ the face of the resulting embedded graph $G^-$ that used to contain the removed vertices and edges. We obtain $\Gamma'_G$ by inserting a drawing of $\pert(\mu)$ whose embedding is $\mathcal E'_\mu$ in the interior of $f$ so that vertices $u_\mu$ and $v_\mu$ are identified with their copies in $G^-$. 

We claim that the embedding $\mathcal E'$ of $\Gamma'_G$ satisfies $m$.
First, the modality of each vertex of $G$ not in $\pert(\mu)$ is the same in $\mathcal E'$ as in $\mathcal E$. Second, the modality of each vertex in $\pert(\mu)$ different from $u_\mu$ and $v_\mu$ is the same in $\mathcal E'$ as in $\mathcal E'_\mu$. 

We only need to show that $u_\mu$ and $v_\mu$ satisfy $m$ in $\mathcal E'$.
We have that $t = \langle \sigma_1, a, \sigma_2, b\rangle $ and $t = \langle \sigma'_1, a', \sigma'_2, b'\rangle$. 
We show that the modality of $u_\mu$ in $\mathcal E'$ is smaller than or equal to the modality of $u_\mu$ in $\mathcal E$; analogous arguments hold for $v_\mu$.
We distinguish two cases. 
If $a$ and $a'$ have the same parity, as shown at vertex $u$ in \cref{fig:substitution}, then $\mathcal E'$ contains an alternating pair consisting of an edge in $G'$ and of an edge in $\pert(\mu)$ incident to $u_\mu$ only if  $\mathcal E$ contains an alternating pair consisting of an edge in $G'$ and of an edge in $\pert(\mu)$ incident to $u_\mu$. Therefore, since $a' \leq a$, the modality of $u_\mu$ in $\mathcal E'$ is smaller than or equal to the modality of $u_\mu$ in $\mathcal E$.
Otherwise, if $a$ and $a'$ have the different parity, as shown at vertex $v$ in \cref{fig:substitution}, then $\mathcal E'$ may contain an alternating pair consisting of an edge in $G'$ and of an edge in $\pert(\mu)$ incident to $u_\mu$ and to the right outer face of $\pert(\mu)$ even if $\mathcal E$ does not contain an alternating pair consisting of an edge in $G'$ and of an edge in $\pert(\mu)$ incident to $u_\mu$. 
However, in this case, it holds that  $a' < a$, therefore the modality of $u_\mu$ in $\mathcal E'$ is again smaller than or equal to the modality of $u_\mu$ in $\mathcal E$.
\end{fullproof}

Let $\calT{}$ be the SPQR-tree $\calT{}$ of $G$ rooted at a reference edge $e$.
In the remainder of the section, we show how to compute the gist $S(\mu)$ of the set of good tuples for $\mu$, for each non-root node $\mu$ of $\calT{}$. In the subsequent procedures to compute $S(\mu)$ for S-, P-, and R-nodes, we are not going to explicitly avoid set $S(\mu)$ to contain dominated tuples. In fact, this can always be done at the cost of an 
additive $O(k^2)$ factor in the running time, by maintaining an hash table that stores the tuples that have been constructed (possibly multiple times) by the procedures and by computing the gist of the constructed set as a final step.

 


\begin{property}\label{obs:size}
For each node $\mu \in \calT{}$, it holds that $|S(\mu)| \in O(k)$.
\end{property}

\begin{proof}
By the definition of gist, any embedding pair $(\sigma,a)$ has at most two tuples $t',t'' \in S(\mu)$ such that $(\sigma,a)$ is the embedding pair of $t'$ and $t''$ at $u_\mu$; also, the embedding pairs $(\sigma',a')$ of $t'$ and $(\sigma'',a'')$ of $t''$ at $v_\mu$ are such that $\sigma' \neq \sigma''$. Since there exist at most $2k$ realizable embedding pairs $(\sigma,a)$ at $u_\mu$ (as $\sigma \in \{\inn,\out\}$, $a \in \{0,1,\dots,k\}$, and the existence of tuple whose embedding pair at $u_\mu$ is $(\sigma,0)$ implies that all tuples have such an embedding pair at $u_\mu$), we have $|S(\mu)| \leq 4k$.\end{proof}

If $\mu$ is a leaf Q-node in $\calT{}$, then $S(\mu)=\{ \langle \sigma(u_\mu v_\mu), 0,  \sigma(u_\mu v_\mu), 0 \rangle \}$.
If $\mu$ is an internal node of~$\calT{}$, we visit $\calT{}$ bottom-up and compute the set $S(\mu)$ for $\mu$ assuming to have already computed the sets $S(\mu_1),\dots, S(\mu_k)$ for the children $\mu_1,\dots,\mu_k$ of $\mu$
(where $\mu_i$ is the child of $\mu$ corresponding to the edge $e_i$ in $\skel(\mu)$).
Let $\rho$ be the unique child of the root of $\calT{}$.
Once the set $S(\rho)$ has been determined, we can efficiently decide whether $G$ admits an embedding satisfying $m$ in which the reference edge $e$ is incident to the outer face by means of the following lemma. 


\begin{lemma}\label{le:rho}
Given $S(\rho)$, we can test whether $G$ has an embedding that satisfies $m$ in $O(k^2)$ time.
\end{lemma}

\begin{fullproof}
Let $t=\langle \sigma_1,a,\sigma_2,b \rangle$ be a realizable tuple in $S(\rho)$ and let ${\cal E}_t$ be the embedding of $G$ obtained by inserting the reference edge $e$ in the outer face of a regular embedding $\cal E_\rho$ of $\pert(\rho)$ realizing $t$ that satisfies $m$. Let $u$ and $v$ be the poles of $\rho$. We have the following claim.

\begin{claim}\label{cl:e_t}
Embedding ${\cal E}_t$ satisfies $m$ if and only if:
\begin{enumerate}[(i)]
    \item
\begin{inparaenum}
    \item $m(u)\geq a+1$, if $a$ is odd, or
    \item $m(u)\geq a$, if $a$ is even and $\sigma_1=\sigma(e)$, \linebreak or
    \item $m(u)\geq a+2$, if $a$ is even and $\sigma_1 \neq \sigma(e)$,
\end{inparaenum} 
and
\item
\begin{inparaenum}
    \item $m(v)\geq b+1$, if $b$ is odd, or
    \item $m(v)\geq b$, if $b$ is even and $\sigma_2=\sigma(e)$, \linebreak or
    \item $m(v)\geq b+2$, if $b$ is even and $\sigma_2 \neq \sigma(e)$.
\end{inparaenum} 
\end{enumerate}
\end{claim}
\begin{fullproof}
\begin{figure}[tb!]
\centering
\subfloat[]{\includegraphics[page=1,height=.24\textwidth]{rootNode}}\hfil
\subfloat[]{\includegraphics[page=2,height=.24\textwidth]{rootNode}}\hfil
\subfloat[]{\includegraphics[page=3,height=.24\textwidth]{rootNode}}
\caption{Illustrations for the proof of \cref{cl:e_t}. (a) The root edge $e$ and $\rho$ (where the orientation of $\rho$ being arbitrary). (b) A $4$-modal embedding of $G$, where $u$ has $2$ alternations and $v$ has $4$ alternations. (b) A $6$-modal embedding of $G$, where $u$ has $4$ alternations and $v$ has $6$ alternations.}
\label{fi:rootNode}
\end{figure}
To prove the statement for vertex $u$, we just need to observe that, if $a$ is odd, then the edges $e'_u$ and $e''_u$ incident to $u$ and to the left and to the right outer face of ${\cal E}_\rho$, respectively, have opposite orientations, while if $a$ if even, then these edges have the same orientation (in this case, possibly $e'_u = e''_u$). Also, since $a$ is the number of alternations between edges incident to $u$ and to the internal faces of ${\cal E}_\rho$, the modality at $u$ in ${\cal E}_\rho$ is equal to $a+1$, if $a$ is odd, while it is equal to $a$, otherwise.
Therefore, since edge $e$ appears between $e'_u$ and $e''_u$ in embedding ${\cal E}_t$ obtained from ${\cal E}_\rho$, we have that the number of alternations around $u$ in ${\cal E}_t$ is the same as in ${\cal E}_\rho$, if $a$ is odd or if $a$ is even and $\sigma(e) = \sigma_1$, and it is equal to the modality of $u$ in ${\cal E}_\rho$ plus $2$, if $a$ is even and $\sigma(e) \neq \sigma_1$. Refer to  \cref{fi:rootNode}. The proof of the statement for vertex $v$ is analogous.
\end{fullproof}

By  \cref{cl:e_t}, for each realizable tuple $t \in S(\rho)$, we can test whether embedding  ${\cal E}_t$ satisfies $m$ in constant time. Also, $|S(\rho)| \in O(k^2)$, by \cref{obs:size}. Therefore, we can test in $O(k^2)$ time whether there exists an embedding of $\pert(\rho)$ that can be extended to an embedding of $G$ that satisfies $m$ in which $e$ is incident to the outer face.
\end{fullproof}

\ifshortversion{}\else{We remark that the choice of the reference edge does not affect the existence of a $4$-modal embedding. In fact, a change of the outer face such that edge $e$ is incident to such a face can always be performed while preserving the rotation at any vertex.}\fi



\section{Partial 2-trees} \label{se:2trees}
In the following, we describe how to compute $S(\mu)$, if $\mu$ is an S-node (\cref{le:S}) and a P-node (\cref{le:P}) in ${O}(f(k)|\skel(\mu)|)$ time, where $f$ is a computable function.

\begin{lemma}\label{le:S}
Set $S(\mu)$ can be constructed in ${O}(k^2|\skel(\mu)|)$ time for an S-node $\mu$.
\end{lemma}

\begin{sketch}
Let $\mu$ be an S-node with skeleton $\skel(\mu)=(e_1,e_2,\dots,e_h)$. We define $\tau_j$ as the S-node obtained by the series composition of $\mu_1, \mu_2,\dots,\mu_j$, with $j \leq h$. Initially we set $S(\tau_1)=S(e_1)$. Then, we construct $S(\tau_j)$ via dynamic programming, for $j=2,\dots,h$, by 
verifying the compatibility of the embedding pairs of the good tuples of the virtual edges of $\skel(\tau_j)$ at the internal vertices of $\skel(\tau_j)$. As $S(\tau_j)=S(\tau_{j-1}) \cup e_j$, we can compute $S(\tau_j)$ by considering all the tuples obtained by combining 
every tuple $t' \in S(\tau_{j-1})$ with every tuple $t'' \in S(e_j)$. Since both these sets contain $O(k)$ tuples, by \cref{obs:size}, and since the tuple resulting from the combination of $t'$ and $t''$ can be determined in $O(1)$ time, we have that $S(\tau_j)$ can be computed in $O(k^2)$ time. Therefore, the overall running \mbox{time for computing $S(\mu)=S(\tau_h)$ is ${O}(k^2 |\skel(\mu)|)$.}
\end{sketch}


\begin{lemma}\label{le:P}
Set $S(\mu)$ can be constructed in $O((2k+4)!k^3 + |\skel(\mu)|)$ time for a P-node~$\mu$.
\end{lemma}

\begin{sketch}
Let $\mu$ be a P-node with poles $u_\mu$ and $v_\mu$, whose skeleton $\skel(\mu)$ consists of $h$ parallel virtual edges $e_1,e_2,\dots,e_h$. 
It can be shown that the computation of $S(\mu)$ reduces in $O(|\skel(\mu)|)$ time to the computation of $S(\tau)$, where $\tau$ is a P-node whose skeleton consists of at most $2k$ virtual edges of $\skel(\mu)$ that contribute with at least one alternating pair of edges at~$u_\mu$ or~$v_\mu$, plus up to $4$ virtual edges of $\skel(\mu)$ that contribute with no alternating pair at~$u_\mu$ or at~$v_\mu$. 
For any permutation $\pi$ of the virtual edges of $\pert(\tau)$, let $\tau^\pi_i$ be the P-node obtained by restricting $\tau$ to the first~$i$ virtual edges in $\pi$. 
We fix the embedding of $\skel(\tau^\pi_i)$ in such a way that the virtual edges of $\skel(\tau^\pi_i)$ are ordered according to $\pi$.
Then, in a fashion similar to the S-node case, we can compute~$S(\tau^\pi_i)$ for the given embedding of $\skel(\tau^\pi_i)$ by combining $S(\tau^\pi_{i-1})$ and $S(e_i)$ in $O(k^2)$ time (recall that both these sets have size $O(k)$, by \cref{obs:size}). 
Clearly, for any fixed $\pi$, we can compute $S(\tau^h_\pi)$ in $O(k^3)$ time. Thus, by performing the above computation for all the $(2k+4)!$ possible permutations for the virtual edges of $\pert(\tau)$, we can construct $S(\tau)$ in $O((2k+4)!k^3+|\skel(\mu)|)$ time.\end{sketch}


Altogether, \cref{le:S,le:P} yield the following main result.

\begin{theorem}\label{th:sp}
\maxkmodality{k} can be solved in $O((2k+4)!k^3  n)$ for series-parallel digraphs.
\end{theorem}


 \cref{obs:reduction}, \autoref{th:simply-to-biconnected}, and \autoref{th:sp} immediately imply the following.

\begin{corollary}\label{co:2trees}
\kmodality{k} can be solved in $O(((2k+4)!k^3\log{k})  n)$ for directed partial $2$-trees.
\end{corollary}

Due to the special algorithmic framework we are employing,
 we can however turn the multiplicative $O(\log{k})$ factor in the running time into an additive $O(k)$ factor by modifying \ifshortversion{\cref{th:simply-to-biconnected} }\else{\cref{algo:simply-to-bico} }\fi as follows. When considering a cut-vertex $v$\ifshortversion{, }\else{ (line~$4$), }\fi we will execute ``only once'' the function {\sc TestBiconnected} \ifshortversion{}\else{(line~$5$) }\fi
 by rooting the SPQ-tree at a Q-node $\eta$ corresponding to an edge incident to~$v$. This will allow us to compute the minimum modality for cut-vertex $v$ in an embedding that satisfies $m$ at every vertex, by simply scanning the set $S(\eta)$, which takes $O(k)$ time by \cref{obs:size}, rather than by exploiting a logarithmic number of calls to {\sc TestBiconnected}.

\begin{theorem}\label{th:2trees-efficient}
\kmodality{k} can be solved in $O((2k+4)!k^3 n)$ for directed partial $2$-trees.
\end{theorem}


\section{A Linear-time Algorithm for 4-MaxModality when $\mathbf{\Delta \leq 6}$} \label{se:deg6} 

In this section, we show that in the special case when $k=4$ and $G$ has maximum degree~$\Delta \leq 6$, it is possible to compute the set $S(\mu)$ when $\mu$ is an R-node in linear time in the size of $\skel(\mu)$. 

Our strategy to compute $S(\mu)$ is as follows.  We select a single tuple from the admissible set of each virtual edge incident to $u_\mu$ and $v_\mu$, in every possible way. Each selection determines a ``\emph{candidate tuple}'' $t$ for $S(\mu)$. 
First, we check if $t$ is admissible at both $u$ and $v$. 
Second, we restrict the tuples of the edges incident to the poles to only the tuples that form $t$ and check if there is a way of satisfying $m$ at the (inner) vertices of $\skel(\mu)$.
If both the poles and the inner vertices are satisfiable, then we add $t$ to $S(\mu)$. Since the degrees of the poles are bounded, there is at most a constant number of candidate tuples which must be checked. The complexity lies in this check.



    We now formally describe how to compute $S(\mu)$.
First, for each virtual edge $e_i$ of $\skel(\mu)$ incident to the poles of $\mu$, we select a tuple $t_i$ from $S(\mu_i)$. 
Let $T_u = [t_{u,1},t_{u,2},\dots,t_{u,\ell}]$ and $T_v=[t_{v,1},t_{v,2},\dots,t_{v,h}]$ be the list of tuples selected for the virtual edges incident to $u_\mu$ and to $v_\mu$, respectively.
Each pair of lists $T_u$ and $T_v$ yields a {\em candidate tuple} $t = \langle \sigma_1, a, \sigma_2, b \rangle$ for $\mu$.
However, the tuples selected to construct $T_u$ and $T_v$ allow for an admissible embedding of $\pert(\mu)$ \mbox{realizing tuple $t$ {\em if and only if}:}
\begin{inparaenum}
    \item[{\bf (Condition~1)}] tuple $t$ satisfies $m$ at $u_\mu$ and at $v_\mu$, and
    \item[{\bf (Condition~2)}] it is possible to select tuples for each of the remaining virtual edges of $\skel(\mu)$ that satisfy $m$ at every internal vertex of $\skel(\mu)$.
\end{inparaenum}
Let $\mathcal P(\mu)$ be the set of candidate tuples for $\mu$ constructed as described above.
We can easily filter out the candidate tuples that do not satisfy Condition~1.
For each pair of lists $T_u$ and $T_v$ yielding a tuple $t \in \mathcal P(\mu)$, we will show how to test Condition~2 for $\mu$ in linear time. This and the fact that $|\mathcal P(\mu)| \in O(1)$ imply the following.


\begin{lemma}\label{le:R}
Set $S(\mu)$ can be constructed in ${O}(|\skel(\mu)|)$ time for an \mbox{R-node}~$\mu$, if $\Delta\leq 6$.
\end{lemma}

Altogether, \cref{le:S,,le:P,,le:R} yield the following main result.

\begin{lemma}\label{le:bico-max-degree}
\maxkmodality{4} can be solved in linear time for biconnected digraphs with $\Delta \leq 6$
\end{lemma}


\cref{obs:reduction}, \cref{th:simply-to-biconnected}, and \cref{le:bico-max-degree} immediately imply the following.

\begin{theorem}\label{th:max-degree}
\mbox{\sc $4$-Modality}\xspace{} can be solved linear time for digraphs with $\Delta \leq 6$
\end{theorem}

To prove \cref{le:R}, we show how to solve the following auxiliary problem for special instances.

\problemdef{\sc $4$-MaxSkelModality}{A triple $\langle G=(V,E), {\cal S}=\{S(e_1),\dots,S(e_{|E|})\}, m \rangle$ where
$G$ is an embedded directed graph, each $S(e_i)$ is a set containing embedding tuples for the virtual edge $e_i \in E$, and $m: V \rightarrow \even{4}$ is the \emph{maximum-modality function}.}{
Can we select a tuple from each set $S(e_i)$ in such a way that the modality at each vertex $v \in V$ is at most $m(v)$?}


\medskip
For each pair of lists $T_u$ and $T_v$ yielding a candidate tuple in $\mathcal P(\mu)$, we will construct an instance $I_\mu(T_u,T_v)=(G,\mathcal S, m)$ of {\sc $4$-MaxSkelModality} as follows.
\begin{inparaenum}
\item We set $G=\skel(\mu)$ and we fix the embedding of $G$ to be equal to the unique regular embedding of $\skel(\mu)$;
\item for each virtual edge $e_{u,i}$ incident to $u_\mu$, with $i=1,\dots,\ell$, we set $S(e_{u,i})=\{t_{u,i}\}$; for each virtual edge $e_{v,j}$ incident to $v_\mu$, with $j=1,\dots,h$, we set $S(e_{v,j})=\{t_{v,j}\}$; for each of the remaining virtual edges $e_d$ of $\skel(\mu)$, we set $S(e_d) = S(\mu_d)$; finally,
\item \mbox{the maximum-modality function of $I_\mu$ coincides with $m$.}
\end{inparaenum}

Clearly, $I_\mu(T_u,T_v)$ is a positive instance of {\sc $4$-MaxSkelModality} if and only if, given the constrains imposed by the tuples in $T_u$ and in $T_v$, there exists a selection of tuples for the edges of $G$ not incident to $u_\mu$ or $v_\mu$ that satisfies $m$ at all the \mbox{internal vertices of $G$, i.e., Condition~2 holds.}


Let $v$ be a vertex of $G$ and let $e$ be an edge in $E(v)$, we denote by $A_v(e)$ the maximum number of alternations at $v$ over all the tuples in~$S(e)$. 


\begin{definition}[Good instances]\label{prop:max6}
An instance of {\sc $4$-MaxSkelModality} is \emph{good} if, for any vertex $v$ in $G$, it holds 
$\sum_{e\in E(v)} (A_v(e)+1) \leq 6$.
\end{definition}

Note that, for each edge $e$ in $ske(\mu)$ incident to a vertex $v$, $\pert(e)$ contributes at least $A_v(e)+1$ edges to $d_{\pert(e)}(v)$. Thus, we have
$\sum_{e\in E(v)} (A_v(e)+1) \leq \sum_{e\in E(v)} d_{\pert(e)}(v) \leq 6$. 
Therefore, instance $I_\mu(T_u,T_v)$ is good.
Although {\sc $4$-MaxSkelModality} turns out to be NP-complete in general \ifshortversion{(