series_parallel_graphs.tex

\chapter{Polynomial-Time Algorithm For Series-Parallel 3-Graphs}\label{ch:sp}
Series-parallel graphs have the nice property that many NP-hard problems turn out to have a polynomial-time solution on them. This section shows that also the problem of finding bend-free or bend-minimum valid ortho-radial representations can be solved in polynomial-time for series-parallel graphs, as long as we consider series-parallel~$3$-graphs.

\begin{figure}
  \centering\includegraphics{figures/sp-graph-composition.pdf}
  \caption{A series composition of two SP-graphs on the left and a parallel composition on the right.}\label{fig:sp-graph-composition}
\end{figure}

\begin{definition}\label{def:spgraphs}
  \emph{Series-parallel graphs (SP-graphs)} with terminals~$s$ and~$t$ are recursively defined as follows.
  \begin{enumerate}
    \item A single edge~$\{s,t\}$ is an SP-graph
    \item Given two SP-graphs~$G_1$ and~$G_2$ with terminals~$s_1,t_1$ and~$s_2,t_2$, then
    \begin{itemize}
      \item the graph~$G$ obtained by identifying~$t_1$ with~$s_2$ is an SP-graph. Such a composition is called a \emph{series composition}. The terminals of~$G$ are~$s_1$ and~$t_2$.
      \item the graph~$G$ obtained by identifying~$s_1$ with~$s_2$ and~$t_1$ with~$t_2$ is an SP-graph. Such a composition is called a \emph{parallel composition}. The terminals of~$G$ are~$s_1=s_2$ and~$t_1=t_2$.
    \end{itemize}
  \end{enumerate}
\end{definition}

\cref{fig:sp-graph-composition} illustrates these two possible compositions. We call a simple path from~$s$ to~$t$ in an SP-graph an \emph{st-path} and we use~$\stpaths$ to denote the \emph{set of all st-path of an SP-graph}~$G$. Because st-paths are simple, they for each parallel composition of an SP-graph at most traverse one of its subgraphs. We now show that the \bendFreeOrthoRadial{}-problem can be solved in polynomial time for series-parallel plane 3-graphs by extending the basic idea of Zhou et al.~\cite{ZHOU05} and Didimo et al.~\cite{DIDIMO22} to the ortho-radial case. We specifically only consider the situation where~$f_o \neq f_c$, as otherwise finding a valid ortho-radial representation degenerates to finding a normal orthogonal representation~\cite{HASHEMINEZHAD}.

In \cref{sec:sp3graph2-leg} we first consider the subset of 2-legged series-parallel plane 3-graph and show that a bend-minimum valid ortho-radial representation can be computed in~$\bigO{n}$ time as long as one exists. \cref{sec:non-st-outwards} covers how this approach can be adapted to search for ortho-radial representations with specific propeties. These are then used in \cref{sec:sp3graphs} to formulate an algorithm for general series-parallel plane 3-graphs, where a bend-free valid ortho-radial representation can, if one exists, be found in~$\bigO{n^2}$ time.

\section{2-Legged Series-Parallel 3-Graphs}\label{sec:sp3graph2-leg}

\begin{figure}
  \centering\includegraphics{figures/2leg-example.pdf}
  \caption{On the left, a 2-legged SP-graph with legs~$e^s$ and~$e^t$ and leg-vertices~$u,v$. On the right, an SP-graph that is not 2-legged as~$\deg(s)\neq1$.}\label{fig:2-leg-example}
\end{figure}

\begin{definition}\label{def:2-legged sp}
  A series-parallel graph~$G$ with terminals~$s$ and~$t$ is called \emph{2-legged} if~$\deg(s)=\deg(t)=1$. The edges incident to~$s$ and~$t$ are called \emph{legs} and are named~$e^s$ and~$e^t$, respectively. The two vertices adjacent to~$s$ and~$t$ are called \emph{leg-vertices}.
\end{definition}
\cref{fig:2-leg-example} shows the difference between a general series-parallel 3-graph and a 2-legged one.
We intentionally diverge from the definition of a 2-legged SP-graph by Zhou et al.~\cite{ZHOU05}, as in their definition they also require the SP-graph to contain at least three vertices. This would specifically exclude the graph consisting of a single edge from being 2-legged. As that would break the possibility of a recursive decomposition of 2-legged SP-graphs, we use the above slightly different definition.

\subsection{Creating Decomposition Trees}

Using the normal decomposition tree of a series-parallel graph for 2-legged series-parallel 3-graphs is not advisable. In such a tree there would exist series nodes that disconnect the edges~$e^s$ and~$e^t$ from the inside of the graph and would eventually decompose it into subgraphs that are not 2-legged anymore. With this, recursive algorithms would get complicated. In the case of 2-legged series-parallel 3-graphs, a different deconstruction is possible that preserves the 2-legged-property. Given a 2-legged series-parallel graph~$G$, the graph~$G-s-t$ obtained by deleting vertices~$s$ and~$t$ is a series-parallel graph having the original leg-vertices as the terminals. We decompose~$G$ into two 2-legged sub-graphs depending on whether~$G-s-t$ is a series or parallel composition similar to the work of Zhou et al.~\cite{ZHOU05}.

\begin{figure}
  \centering\includegraphics[]{figures/2leg-series-composition.pdf}
  \caption{On the left, a 2-legged SP-graph consisting of two subgraphs~$G_1'$ in blue and~$G_2'$ in red as by the normal composition rules of SP-graphs. On the right, the subgraphs~$G_1$ and~$G_2$ resulting from the decomposition into 2-legged SP-graphs. For~$G_1$ to be 2-legged, it receives a copy of the edge~$e$.}\label{fig:2-leg-series-decomp}
\end{figure}

\begin{lemma}\label{lem:2-legged-series-comp}
  Let~$G$ be a 2-legged series-parallel 3-graph where~$G-s-t$ is a series composition of two subgraphs~$G_1'$ and~$G_2'$. Then~$G$ can be deconstructed into two subgraphs~$G_1$ and~$G_2$ that only share a single edge~$e$ and are both 2-legged series-parallel 3-graphs.
\end{lemma} 
\begin{proof}
  Let~$w$ be the single vertex connecting the subgraphs~$G_1'$ and~$G_2'$. Without loss of generality, as~$\deg(w) \leq 3$,~$G_2'$ contains only a single edge~$e$ incident to~$w$ as seen in \cref{fig:2-leg-series-decomp}. Defining~$G_1 \defeq G_1' \cup \{e\}$ and~$G_2 \defeq G_2'$ we get two 2-legged series-parallel subgraphs. 
\end{proof}
In this decomposition, we require series nodes to have exactly two children. A series connection of more than two subgraphs has to be represented by a sequence of series nodes. Note that in a normal series composition, the two subgraphs share a single vertex, whereas in the decomposition of \cref{lem:2-legged-series-comp}, the resulting subgraphs share a single edge. When connecting two 2-legged SP-graphs~$G_1,\ G_2$ in series,~$e^t$ of~$G_1$ and~$e^s$ of~$G_2$ therefore get merged into a single edge (see edge~$e$ in \cref{fig:2-leg-series-decomp}).

\begin{lemma}\label{lem:2-legged-parallel composition}
  Let~$G$ be a 2-legged series-parallel 3-graph where~$G-s-t$ is a parallel composition of multiple subgraphs. Then~$G$ can be deconstructed into exactly two subgraphs~$G_1$ and~$G_2$ both of which are 2-legged series-parallel 3-graphs.
\end{lemma}
\begin{proof}
  Let~$u,v$ be the two leg-vertices of~$G$. As~$\deg(u),\deg(v)\leq 3$ and~$u,v$ already have the incident edges~$e^s$ and~$e^t$, there are exactly two children in the parallel composition. Each child is connected to~$v$ and~$u$ with a single edge and is therefore 2-legged.
\end{proof}
\begin{figure}
  \centering\includegraphics[]{figures/2leg-decomp-example.pdf}
  \caption{A 2-legged SP-graph and its decomposition tree. The order of the children in the tree represents the embedding of the graph and the marked node indicates the parallel composition where~$f_c$ is formed.}\label{fig:2-leg-decomp}
\end{figure}
With this knowledge, a 2-legged series-parallel 3-graph~$G$ can be represented by a decomposition tree similar to general SP-graphs. An~$\node{S}$-node represents a series and~$\node{P}$-node a parallel composition of two 2-legged subgraphs, where both always have two subgraphs. There also exist two types of leaf nodes. A~$\node{Q}$-node, similar to normal decomposition trees, represents a single edge and a~$\node{D}$-node represents two connected series edges. \cref{fig:2-leg-decomp} shows an example of a decomposition tree. Note that the second type of leaf node is required for these kinds of decomposition trees. This is because a~$\node{D}$-node (two adjacent edges) is not the result of a series composition of two~$\node{Q}$-nodes as would be the case for normal decomposition trees. A series composition of two 2-legged SP-graphs always merges one leg of one subgraph with another leg of the other subgraph into a single edge. Therefore, a series composition with a~$\node{Q}$-node is in fact an identity operation. Connecting two~$\node{Q}$-nodes serially together would again simply result in another~$\node{Q}$-node, so a~$\node{D}$-node is necessary. The creation of a decomposition tree for a 2-legged SP-graph is, per step, based on the creation of a normal decomposition tree. Therefore, a linear-time algorithm for constructing a 2-legged decomposition tree can be easily deduced from the literature.

We now also restrict the set of embeddings we consider. Specifically, we require for the given fixed embedding~$\emb$ that the terminals of~$G$ are incident to the outer face~$f_o$. We say that~$\emb$ is an \emph{outer embedding} of~$G$ if this is given. With~$\emb$ being an outer embedding, the order of the children in the tree completely describe~$\emb$ as follows. If a vertex~$v$ has a degree of~$2$ or lower, its rotation scheme is already fixed. If its degree is~$3$, it must be the leg-vertex of some~$\node{P}$-node~$\phi$. The fact that~$\emb$ is outer together with the ordering of the child nodes implies an order of the incident edges of~$v$ and therefore a rotation scheme of~$v$. The embedding described in \cref{fig:2-leg-decomp} is outer and the order of the children in the decomposition tree reflects the embedding of the graph.

A~$\node{Q}$-node is \emph{marked} if at the connection of its children the central face~$f_c$ is formed (again see \cref{fig:2-leg-decomp}) and a node contains~$f_c$ if it contains the marked node in its subtree. These are exactly all nodes in the direct path from the marked~$\node{Q}$-node to the root node. The problem instance of~$(G,\emb,f_o,f_c)$ can now be completely represented by a decomposition tree of~$G$. From now on, unless specified otherwise, 2-legged SP-graphs always have a maximum degree of~$3$, an embedding is always outer, and a decomposition tree of a 2-legged SP-graph refers to the above-mentioned new type of decomposition tree. A node~$\phi$ is said to \emph{induce} a 2-legged SP-graph~$G$ if~$G$ has a decomposition tree with~$\phi$ as its root. Moreover, if~$G$ is rectilinear-plane with the fixed embedding of~$\phi$, we also say that~$\phi$ is rectilinear-plane and if~$G$ is orthoradial-plane with the fixed embedding of~$\phi$, we say that~$\phi$ is orthoradial-plane. 

\subsection{Finding Bend-Free Ortho-Radial Representations}


The general idea in this chapter is to traverse the decomposition tree of a 2-legged SP-graph~$G$ in a bottom-up fashion while keeping track of which orthogonal or ortho-radial representations are achievable at each node. As only some properties of these representations are important for the recursion, only these are tracked. Before defining which properties are needed, we define the notion of \emph{relative labels}. A relative label is similar to the labelling in an ortho-radial representation but with a variable reference edge. We will use relative labels in the construction of our proofs rather than normal labels since the actual reference edge in the to-be-found valid ortho-radial representation may not yet be present in some steps of the recursion.

\begin{lemma}\label{lem:2-legged-rellabel-welldefined}
  Let~$(G,\emb)$ be a 2-legged series-parallel plane 3-graph,~$\ogr$ an orthogonal representation of~$G$ and~$e^*$ an edge in~$G$. Let~$e \in G$ be an edge for which there exists an st-path~$P$ first traversing~$e^*$ and then traversing~$e$. Then~$\rot(P[e^*,e])$ is independent of the choice of~$P$.
\end{lemma}
\begin{proof}
   Let~$P_1$ and~$P_2$ be two st-paths both first traversing~$e^*$ and afterwards~$e$. One has to now show that~$\rot(P_1[e^*,e]) = \rot(P_2[e^*,e])$.
  For this, let~$G'$ be the subgraph~$P_1[e^*,e] \cup P_2[e^*,e] \subseteq G$ consisting only of the two alternative paths between~$e^*$ and~$e$. As~$G'$ is a subgraph of~$G$, it can be associated with the induced orthogonal representation of~$\ogr$. Then~$P_1[e^*,e]$ and~$P_2[e^*,e]$ are both so-called spines of~$G'$, and~$\rot(P_1[e^*,e]) = \rot(P_2[e^*,e])$ follows from the literature~\cite[Lemma 4.1]{BATTISTA98}. 
\end{proof}

\begin{definition}\label{def:2-legged-rellabel}
  Let~$(G,\emb)$ be a 2-legged series-parallel plane 3-graph,~$\ogr$ an orthogonal representation of~$G$ and~$e^*$ an edge in~$G$. Let~$e \in G$ be an edge for which there exists an st-path~$P$ first traversing~$e^*$ and then traversing~$e$. Then~$\lref{e^*}{e}$ is called the \emph{label} of~$e$ \emph{relative} to~$e^*$ in~$\ogr$ and is defined as
  \[\lref{e^*}{e} \defeq \rot(P[e^*,e]).\]
  We further define~$\lref{s}{e} \defeq \lref{e^s}{e}$.
\end{definition}
Unless specified otherwise, a relative label of some edge in a 2-legged SP-graph always refers to the label relative to~$e^s$. As relative labels are defined via rotations on paths, we also know that if an st-path contains three edges~$e, f, g$ in this order, then
\[\lref{e}{g} = \lref{e}{f} + \lref{f}{g}.\]
 
We now define the specific properties of nodes in the tree that have to be tracked. As will be shown later, it is enough to only define properties for nodes not yet containing~$f_c$. For these nodes, the definition of orthogonal representations and (valid) ortho-radial representations are equivalent. First, we have to make sure that when connecting two subgraphs together, there exist representations of the subgraphs that can be connected to form a representation of the whole graph. 
To do this, the approach of Didimo et al.~\cite{DIDIMO22} is used. They also find bend-minimum drawings of SP-graphs using decomposition trees but only in the orthogonal case. They found that per node they only have to keep track of the \emph{spirality} of the induced subgraph to tell if and how many bends are required for the parent node to admit an orthogonal representation as well.

The spirality~$\sigma(\ogr)$ of an orthogonal representation~$\ogr$ was first introduced by Di Battista et al.~\cite{BATTISTA98}. They define it, at least in the case of 2-legged SP-graphs, as~$\sigma(\ogr)=\rot(P)$ for an st-path~$P\in \stpaths$. For general graphs, the definition is slightly more complicated. \cref{lem:2-legged-rellabel-welldefined} also implies that the spirality is indipendent of the concrete st-path. With the definition of relative labels, the spirality of~$\ogr$ could also be defined as~$\sigma(\ogr) = \lref{s}{e^t}$. Spirality essentially measures how much a graph is curled up in a given orthogonal representation. The following lemma shows that for 2-legged series-parallel plane 3-graphs, an orthogonal representation of the graph can, intuitively speaking, always be unraveled such that it is less curled up.
\begin{lemma}\label{lem:unbend}
  Let~$(G,\emb)$ be a 2-legged series-parallel plane 3-graph for which an orthogonal representation~$\ogr$ of~$G$ exists with~$\sigma(\ogr)=x \neq 0$.
  Then for every~$y \in \{0,\hdots, x-1\}$, if~$x$ is positive, or~$y \in \{x+1,\hdots,0\}$, if~$x$ is negative, there exists an orthogonal representation~$\ogr_y$ of~$G$ with~$\sigma(\ogr_y) = y$.
\end{lemma}
\begin{proof}
For positive~$x$, this fact is proven by Di Battista et al.~\cite[Lemma 5.1, Lemma 5.2]{BATTISTA98} as~$G$ is a 3-graph. They later argue that the mirrored result for negative~$x$ also holds.
\end{proof}
\cref{lem:unbend} implies that the set of possible spirality values for a 2-legged SP-graph is an interval.
As also done by Didimo et al.~\cite{DIDIMO22}, a node keeps track of the maximum and minimum spirality values possible over all orthogonal representations of a graph. We call the minimum possible spirality of the graph its \emph{left bend value} and the maximum possible spirality the \emph{right bend value}.

\begin{definition}\label{def:bendvalues}
  Let~$(G,\emb)$ be a \twlegrecplsptg. Then the \emph{left bend value}~$b^l$ and the \emph{right bend value}~$b^r$ of~$G$ are defined as
  \begin{align*}
    b^l &\defeq -\min \{\sigma(\ogr)\ |\ \ogr \in \Omega(G,\emb) \} \text{ and}\\
    b^r &\defeq  \max \{\sigma(\ogr)\ |\ \ogr \in \Omega(G,\emb)\}.
  \end{align*}
\end{definition}
Intuitively, the value~$b^l$ indicates how much the graph can curl up to the left relative to~$e^s$, and~$b^r$ indicates how much it can curl up to the right. \cref{fig:2-leg-values-example} shows two sample graphs and their bend values. \begin{lemma}\label{cor:bendbetween}
  Let~$(G,\emb)$ be a \twlegrecplsptg{} and let~$b^l$ and~$b^r$ be its step values. We then know that~$b^l\geq 0$ and that for every~$y \in \{-b^l,\hdots,b^r\}$ there exists an orthogonal representation~$\ogr_y$ of~$G$ with~$\sigma(\ogr_y)=y$.
\end{lemma}
\begin{proof}
  Both statements directly follow from \cref{def:bendvalues} and \cref{lem:unbend}.
\end{proof}

\begin{figure}
  \centering\includegraphics[]{figures/2leg-values-example.pdf}
  \caption{Two 2-legged SP-graphs and orthogonal representations corresponding to their bend and step values. If some step value is~$0$, no matching orthogonal representation exists.}\label{fig:2-leg-values-example}
\end{figure}

Bend values would be enough in the orthogonal case, but to satisfy the labeling-constraint of a valid ortho-radial representation more information about the internal structure of each subgraph is required. At some~$\node{P}$-nodes in the recursion essential cycles may be formed by connecting two subgraphs in parallel We have to make sure that these do not become invalid cycles. A cycle is valid if it contains a positively- and negatively-labelled edge or if it only consists of edges with label~$0$. To ensure this, we are interested in a few subsets of special orthogonal representations of each subgraph. Namely, those where in every st-path there exists an edge with a negative (resp. positive) label relative to the starting terminal, and those where an st-path exists consisting of only edges with a relative label of~$0$. We define these special subsets for a \twlegrecplsptg{}~$(G,\emb)$ as
\[{\Omega_-(G,\emb)} \defeq \{\ogr \in \Omega(G,\emb)\ |\ \forall P \in \stpaths : \exists e \in P: \lrefs{e}<0\}\]
for the subset of orthogonal representations containing an edge with a negative relative label in every st-path and
\[{\Omega_+(G,\emb)} \defeq \{\ogr \in \Omega(G,\emb)\ |\ \forall P \in \stpaths : \exists e \in P: \lrefs{e}>0\}\]
for the subset of orthogonal representations containing an edge with a positive relative label in every st-path. Finally, we use
\[{\Omega_z(G,\emb)} \defeq \{\ogr \in \Omega(G,\emb)\ |\ \exists P \in \mathcal{P}_{st}(G): \forall e \in P:\lrefs{e}=0\}\]
for the subset of orthogonal representations where an st-path exists consisting of only edges with relative label~$0$. The correlation between relative labels and spirality implies that every orthogonal representation in~${\Omega_z(G,\emb)}$ has spirality~$0$. But the orthogonal representations in the other two set are allowed to have different spirality values. Similar to bend values, we need to know the range of spirality values achievable in these subsets. For this, we introduce the notion of \emph{step values}.


\begin{definition}\label{def:stepvalues}
  Let~$(G,\emb)$ be a \twlegrecplsptg. We define the following three \emph{step values}.
  \begin{enumerate}
    \item The \emph{left step value}~$s^l$ is defined as 
    \[s^l \defeq \max(\{0\} \cup \{\sigma(\ogr)+1\ |\ \ogr \in {\Omega_-(G,\emb)}\}).\]
    \item The \emph{right step value}~$s^r$ is defined as
    \[s^r \defeq \max(\{0\}\cup\{-\sigma(\ogr)+1\ |\ \ogr \in {\Omega_+(G,\emb)}\}).\]
    \item The \emph{zero step value}~$s^z \in \{0,1\}$ is defined as
    \[s^z = \begin{cases}
      1 \caseif {\Omega_z(G,\emb)} \neq \emptyset,\\
      0\caseotherwise.
    \end{cases}.\]
  \end{enumerate}
\end{definition}
 Observe that we intentionally add~$1$ to the spirality in the definition of~$s^l$ and~$s^r$. This is done to differentiate between the case~$s^l=0$, which implies that no orthogonal representation in~${\Omega_-(G,\emb)}$ exists with a spirality of~$0$ or greater, and the case~$s^l>0$, where an orthogonal representation~$\ogr$ in~${\Omega_-(G,\emb)}$ exists with~$\sigma(\ogr)=s^l-1\geq 0$. To get a feel for step values, \cref{fig:2-leg-values-example} depicts two examples of 2-legged SP-graphs and their corresponding step values. As seen in the figure, the left and right step values may differ. This is due to the fact that we are given a fixed embedding. The benefits of step-values can be seen in the following example. If~$s^l=1$ for some subgraph~$G$, we know that an orthogonal representation~$\ogr$ of~$G$ exists with~$\sigma(\ogr)=0$ and an edge in every st-path with a negative relative label. If an ortho-radial representation of the complete graph exists containing~$\ogr$ and the leg~$e^s$ of~$G$ is oriented to have label~$0$, every essential cycle traversing~$G$ must completely traverse some st-path of~$G$ and therefore contains at least one negatively-labelled edge.

Now, for every tree node~$\phi$ that does not yet contain the central face~$f_c$ we keep track of both bend and step values in a tuple~$[b^l,b^r,s^l,s^r,s^z]$ called the \emph{\structure{} of~$\phi$}. For tree nodes that already contain the central face no further information is required.
As a base case for the recursion, we assign to every~$\node{Q}$-node the \structure{} 
\[[b^l,b^r,s^l,s^r,s^z] = [0,0,0,0,1]\]
and to every~$\node{D}$-node the \structure{}
\[[b^l,b^r,s^l,s^r,s^z] = [1,1,0,0,1].\]
Before actually looking at the recursion itself, further insight into the properties of bend and step values are required. Given some orthogonal representation~$\ogr$ of a graph~$G$ we know from \cref{lem:unbend} that~$b^r \geq \sigma(\ogr)$ and~$b^l \geq -\sigma(\ogr)$. But sometimes further properties of~$\ogr$ are deducible that improve on these simple inequalities. 
\begin{lemma}\label{lem:2-leg-elementarytransform}
  Let~$(G,\emb)$ be a \twlegrecplsptg{} and let~$\ogr$ be an orthogonal representation of~$G$ with~$x \defeq \sigma(\ogr)$. Then the following holds.
\begin{itemize}
  \item If in every st-path~$P$ there exist adjacent vertices~$u,v,w$ such that~$\rot(uv,vw) = 1$, then there exists another orthogonal representation~$\ogr'$ of~$G$ with~$\sigma(\ogr') = x-1$ and therefore~$b^l\geq x+1$.
  \item If in every st-path~$P$ there exist adjacent vertices~$u,v,w$ such that~$\rot(uv,vw) = -1$, then there exists another orthogonal representation~$\ogr'$ of~$G$ with~$\sigma(\ogr') = x+1$ and therefore~$b^r\geq x+1$.
\end{itemize}
In both cases,~$\ogr'$ and~$\ogr$ differ per st-path only in the rotation at exactly one vertex~$v$ having the above requirements. All other rotations stay the same.
\end{lemma}
\begin{figure}
  \centering\includegraphics[]{figures/2leg-elementary-transformation.pdf}
  \caption{On the left, an orthogonal representation that contain a positive rotation in every st-path indicated by a blue angle. Next to it the result of \cref{lem:2-leg-elementarytransform}, where the spirality of the new representation was decreased by~$1$. On the right, the same orthogonal representations with negative rotations in every st-path indicated by red angles and similarly the resulting graph with now a higher spirality.}\label{fig:2-leg-elem-trans-example}
\end{figure}
\begin{proof}
  Only the proof for the first half is given, since the other half is simply the mirrored result. Let~$\ogr$ be an orthogonal representation of~$G$ with~$\sigma(\ogr)=x$,where every st-path contains adjacent vertices~$u,v,w$ such that~$\rot(uv,vw) = 1$ (see \cref{fig:2-leg-elem-trans-example}). The following proof is an adaption to the one by Di Battista et al.~\cite[Lemma 5.2]{BATTISTA98}. They show that given an orthogonal representation with positive spirality~$y$, an orthogonal representation with spirality~$y-1$ can be created by finding a correctly oriented elementary transformation as defined by Tamassia et al.~\cite{TAMMASSIA91}. They show this for general planar 3-graphs and their notation is therefore slightly different. Instead of using st-paths they use the more general notion of splines. In our case though, they are equivalent. Their proof depends on the existence of a so-called access in every st-path of the graph, where the source face of the access is locally to the left of the st-path and the target is to the right. An access is a vertex~$a$ with source face~$f$ and target face~$g$ if one of the following two cases holds. 
  \begin{enumerate}
    \item  If vertex~$a$ has exactly two incident faces~$f_1$ and~$f_2$ and the rotation of face~$f_1$ at~$a$ is not~$1$, then~$a$ is an access from~$f_1$ to~$f_2$.
    \item If vertex~$a$ has three incident faces~$f_1, f_2$, and~$f_3$ and the rotation of face~$f_1$ at~$a$ is zero, then~$a$ is an access from~$f_1$ to both~$f_2$ and~$f_3$.
  \end{enumerate}

  \begin{figure}
    \centering\includegraphics[]{figures/2leg-elementary-transf-access.pdf}
    \caption{The three possibilities of an access from the face~$f_1$ on the left of the st-path~$P$ to the face~$f_2$ on the right at the vertex~$v$. For every case the rotation at~$v$ along~$P$ is positive. Next to each drawing is the result of an elementary transformation using the access~$v$.}\label{fig:2-leg-elem-trans}
  \end{figure}

  Now let~$v$ be the vertex in an arbitrary st-path~$P$ with the requirements given in the statement (see \cref{fig:2-leg-elem-trans}). As~$\rot(uv,vw)=1$, then only one incident face of~$v$ can lie locally to the right of~$P$. If also~$\deg(v)=2$, then only two faces are incident to~$v$ and the other incident face has a rotation of~$-1$ at~$v$. If~$\deg(v)=3$, then exactly one of the now two other incident faces has a rotation of~$0$ at~$v$. In any case,~$v$ is in an access from the left side of~$P$ to the right side.  As~$P$ was arbitrary, every st-path contains a correctly oriented access.
  Di Battista et al.~\cite{BATTISTA98} only require the orthogonal representation to have a positive spirality in their lemma so they can later argue that every st-path must contain a correctly oriented access. As this is already given in our case, we can, even with having~$\sigma(\ogr) = x\leq 0$, deduce that another orthogonal representation~$\ogr'$ of~$G$ must exist with~$\sigma(\ogr) = x - 1$.

  The elementary transformation used in the proof by Di Battista et al.~\cite{BATTISTA98} only traverses one access per st-path. As only traversed vertices are changed, all other rotations in~$\ogr$ stay the same.
\end{proof}
\begin{lemma}\label{lem:2-leg-brgreatersl}
  Let~$(G,\emb)$ be a \twlegrecplsptg{} having the \structure{}~$[b^l,b^r,s^l,s^r,s^z]$. Then~$b^r \geq s^l$ and~$b^l \geq s^r$.
\end{lemma}
\begin{proof}
  Let~$x=s^l>0$. Then there exists an orthogonal representation~$\ogr$ of~$G$ with~$\sigma(\ogr)=x-1$ and every st-path contains an edge~$e$ with~$\lrefs{e}<0$. Let~$P$ be an arbitrary st-path. For~$P$ to have a relative label of~$0$ at~$e^s$ and a negative label at the edge~$e$ with~$\lrefs{e}<0$, there must exist three adjacent vertices~$u,v,w$ in~$P$ between~$s$ and~$e$ with~$\rot(uv,vw)=-1$. \cref{lem:2-leg-elementarytransform} then implies~$b^r \geq x = s^l$. For~$s^r$ this follows analogously.
\end{proof}
\begin{lemma}\label{lem:2-leg-b0-implies-s0}
  Let~$(G,\emb)$ be a \twlegrecplsptg{} having the \structure{}~$[b^l,b^r,s^l,s^r,s^z]$. Then~$s^l = 0$ if~$b^l =0$, and~$s^r = 0$ if~$b^r=0$.
\end{lemma}
\begin{proof}
  We make a proof by contraposition. Assume~$s^l > 0$. Then there exists an orthogonal representation~$\ogr$ of~$G$ with~$\sigma(\orr)=0$ and an edge with a negative relative label in every st-path of~$G$. Let~$P$ be an arbitrary st-path and let~$e$ be an edge with a negative relative label in~$P$. Then for~$0=\sigma(\orr)=\lrefs{e^t}$ to hold, the labels on the path must go from a negative relative label at~$e$ to a relative label of~$0$ at~$e^t$. So there must exist three adjacent vertices~$u,v,w$ between~$e$ and~$e^t$ with~$\rot(uv,vw)=1$. \cref{lem:2-leg-elementarytransform} then implies~$b^l \geq 0 +1 > 0$. For~$s^r$ and~$b^r$ this follows analogously.
\end{proof}
\begin{lemma}\label{lem:2-leg-bgeq2IfBothPosAndNeg}
  Let~$(G,\emb)$ be a \twlegrecplsptg{} and let~$\ogr$ be an orthogonal representation of~$G$ where every st-path contains an edge with a positive and an edge with a negative relative label. If~$\sigma(\ogr)\leq 0$, then~$b^l \geq 2$. Similarly, if~$\sigma(\ogr)\geq 0$, then~$b^r \geq 2$.
\end{lemma}
\begin{proof}
  As a start, consider the case~$\sigma(\ogr) = 0$ and let~$P$ be an arbitrary st-path in~$G$. Without loss of generality,~$P$ contains first an edge~$e$ with a negative and then an edge~$f$ with a positive label. Then~$P$ has to contain adjacent vertices~$u,v,w$ between~$s$ and~$e$ as well as~$u',v',w'$ between~$f$ and~$e$ with~$v \neq v'$ and~$\rot(uv,vw)=\rot(u'v',v'w')=-1$. Moreover,~$P$ must also contain adjacent vertices~$x,y,z$ and~$x',y',z'$ between~$e$ and~$f$ with~$y\neq y'$ and~$\rot(xy,yz)=\rot(x'y',y'z')=1$. Looking at the vertex~$v$ in every path, \cref{lem:2-leg-elementarytransform} implies the existence of another orthogonal representation with spirality~$1$. As in the new orthogonal representation only the rotations at each~$v$ may be different,~$\rot(u'v',v'w')=-1$ still holds. Therefore, \cref{lem:2-leg-elementarytransform} implies the existence of a third orthogonal representation, now with spirality~$2$, and~$b^r \geq 2$ follows. The same argument with~$y$ and~$y'$ implies~$b^l \geq 2$.

  Now if~$ x= \sigma(\ogr) \geq 1$, there must still exist adjacent vertices~$u,v,w$ in every path with~$\rot(uv,vw)=-1$. It follows again with \cref{lem:2-leg-elementarytransform} that~$b^r\geq x+1 = 2$. The same applies if~$\sigma(\ogr) \leq 1$, where there still exist adjacent vertices~$x,y,z$ in every path with~$\rot(xy,yz)=1$.
\end{proof}
\begin{figure}
  \centering\includegraphics[]{figures/2-leg-omega-proof.pdf}
  \caption{Two st-paths~$P$ and~$Q$. Between~$e$ and~$f$ the paths are disjoint and after~$f$ the paths coincide. The cycle~$C$ is formed by connecting the subpaths~$P[e_P,f_P]$ and~$\overline{Q[e_Q,f_Q]}$.}\label{fig:2-leg-omega-proof}
\end{figure}
\begin{lemma}\label{lem:oneofslsrs0}
  Let~$(G,\emb)$ be a \twlegrecplsptg. Then 
  \[{\Omega_-(G,\emb)} \cup {\Omega_+(G,\emb)} \cup {\Omega_z(G,\emb)} =\Omega(G,\emb).\]
\end{lemma}
\begin{proof}
  It is clear From the definition of each set that the ''$\subseteq$''-direction must hold. To prove the ''$\supseteq$''-direction, we show that if an orthogonal representation~$\ogr$ of~$G$ is neither contained in~${\Omega_-(G,\emb)}$ nor in~${\Omega_+(G,\emb)}$, it must be contained in~${\Omega_z(G,\emb)}$. Let~$\ogr$ be an orthogonal representation of~$G$ with~$\ogr \notin {\Omega_-(G,\emb)} \cup {\Omega_+(G,\emb)}$. Then there exists an st-path~$P$ in~$G$ where~$\lrefs{e}\geq 0$ for all~$e \in P$. There also exists an st-path~$Q$ in~$G$ where~$\lrefs{e}\leq 0$ for all~$e \in Q$. Now as~$e^t$ is contained in both~$P$ and~$Q$, it follows that~$0 \geq \lrefs{e^t} \geq 0$ and therefore~$\sigma(\ogr)= \lrefs{e^t} = 0$.
  What is left is to prove the existence of an st-path having only zero-labelled edges and in fact, we show that~$P=Q$ and this path has the desired property. As~$e^t$ is contained in both paths and has relative label~$0$, we can define~$f$ to be the first edge in~$P$ and~$Q$ at and after which both paths coincide. Just as for~$e^t$ we know that~$f$ and every edge after~$f$ has relative label~$0$. Now if~$f=e^s$, then both paths would coincide in their whole length and the statement would already hold. So assume~$f\neq e^s$. Then the following situation, as also seen in \cref{fig:2-leg-omega-proof}, would arise. There exists a predecessor~$f_P$ of~$f$ in~$P$ and a predecessor~$f_Q$ of~$f$ in~$Q$ with~$f_Q \neq f_P$. Let also~$e$ be the first edge preceding~$f_P$ in~$P$ and~$f_Q$ in~$Q$ that is contained in both paths again, and let~$e_P$ be the successor of~$e$ in~$P$ and~$e_Q$ be the successor of~$e$ in~$Q$. Then~$P[e_P,f_P] + \overline{P[e_Q,f_Q]}$ forms a simple cycle~$C$. The orientation of the cycle implied by the two subpaths may be such that its interior is not locally to the right, but to the left. By the definition of orthogonal representations it follows that~$\rot(C)$ is either~$4$ if the interior is to the right or~$-4$ if it is to the left.
  Regarding the part~$P[e_P,f_P]$ it follows that
  \begin{multline*}
     \rot(P[e_P,f_P])=\infoMath{\lref{s}{e_P} + \lref{e_P}{f_P} + \lref{f_P}{f}}{=\lrefs{f}=0} - \lref{s}{e_P} - \lref{f_P}{f}\\
    =-\lref{s}{e} - \rot(e,e_P) - \rot(f_P,f).
  \end{multline*}
  Similarly,~$\rot(\overline{P[e_Q,f_Q]}) = \lref{s}{e} + \rot(e,e_Q) + \rot(f_Q,f)$ follows. As~$e,e_P$, and~$e_Q$ share the same incident vertex, it follows from the definition of an orthogonal representation that~$\rot(e,e_P)$ and~$\rot(e,e_Q)$ are not both~$0$ at the same time. The same is true for~$\rot(f_P,f)$ and~$\rot(f_Q,f)$. Then it follows that
  \begin{multline*}
     \rot(C) = \rot(P[e_P,f_P]) + \rot(\overline{P[e_Q,f_Q]}) \\
    =\infoMath{\rot(e,e_Q) - \rot(e,e_P)}{\in\{-2,-1\}} + \infoMath{\rot(f_Q,f) - \rot(f_P,f)}{\in \{1,2\}} \in [-1,1].
  \end{multline*}
  This contradicts~$\rot(C)\in \{-4,4\}$ and therefore~$e=e^s$, which implies that~$P$ is equal to~$Q$ and the paths only contain zero-labelled edges.
\end{proof}

\begin{lemma}\label{lem:2leg-s^z-other-paths}
  Let~$(G,\emb)$ be a \twlegrecplsptg{} having an orthogonal representation~$\ogr$ of~$G$ where there exists an st-path containing only edges with relative label~$0$. Then every other st-path contains both an edge with a positive and an edge with a negative relative label.
\end{lemma}
\begin{proof}
  Let~$P$ be the st-path containing only edges with relative label~$0$ and let~$Q$ be an arbitrary other st-path of~$G$. Let~$v$ be the vertex where~$P$ and~$Q$ split up and let~$w$ be the vertex where they meet again. These vertices are never the terminals and both paths share a common edge~$e$ before~$v$ and a common edge~$f$ after~$w$. Let also~$e_P$ and~$e_Q$ be the edges after~$e$ in~$P$ and~$Q$ and let~$f_P$ and~$f_Q$ be the edges before~$e$ in~$P$ and~$Q$. We then know that~$\lrefs{e}=\lrefs{w}=0$. As the edges~$e_P$ and~$f_P$ also have relative label~$0$ we know that~$\lrefs{e_Q}=1$ if~$e_Q$ lies locally to the right of~$P$ and~$\lrefs{e_Q}=-1$ if~$e_Q$ lies locally to the left. Similarly, we know~$\lrefs{f_Q}=-1$ if~$f_Q$ lies locally to the right and~$\lrefs{f_Q}=1$ if it lies locally to the left. It is impossible that~$e_Q$ and~$f_Q$ lie locally on different sides of~$P$, as then either~$s$ or~$t$ is not contained in~$f_o$. This would be a contradiction to~$\emb$ being an outer embedding and therefore,~$Q$ always contains edges with positive and negative relative labels.
\end{proof}

Similar to the work of Didimo et al.~\cite{DIDIMO22}, the \structure{} of an inner node can be described with respect to the \structure{}s of its children. We now often rely on the Iversion bracket notation to formulate these relationships. When multiplying an Iversion bracket with some other term, the boolean expression in the bracket essentially acts as a condition for the term. If we for example have~$(s^l+b^r)\cdot[s^l > 0]$ containing the left step and right bend value we get the following equality.
\[(s^l+b^r)\cdot[s^l > 0] = \begin{cases}
  (s^l + b^r) \caseif s^l > 0,\\
  0 \caseotherwise
\end{cases}\] 

\begin{lemma}\label{lem:2-leg-series-value}
  Let~$\phi$  be an~$\node{S}$-node not containing~$f_c$, where its children~$\phi_1$ and~$\phi_2$ both are rectilinear-plane. Also, let~$\mstructure{1}$ be the \structure{} of~$\phi_1$ and~$\mstructure{2}$ be the \structure{} of~$\phi_2$. Then~$\phi$ is also rectilinear-plane and the \structure{}~$[b^l,b^r,s^l,s^r,s^z]$ of~$\phi$ satisfies the following.
  \begin{align*}
    b^l &= b_1^l+b_2^l \\
    b^r &= b_1^r+b_2^r 
  \end{align*}
    \begin{numcases}{s^l = \max}
      s_2^l,\label{eq:-2leg-series-value-sl1}\\ 
      b_2^r \cdot [b_1^l > 0],\label{eq:-2leg-series-value-sl2}\\
      (s_1^l + b_2^r) \cdot [s_1^l > 0]\label{eq:-2leg-series-value-sl3}  
    \end{numcases}
    \begin{numcases}{s^r = \max}
      s_2^r,\label{eq:-2leg-series-value-sr1}\\
      b_2^l \cdot [b_1^r> 0],\label{eq:-2leg-series-value-sr2}\\
      (s_1^r + b_2^l) \cdot [s_1^r> 0]\label{eq:-2leg-series-value-sr3}
    \end{numcases} 
    \begin{align}
      s^z = s_1^z \cdot s_2^z \label{eq:-2leg-series-value-s0}
    \end{align}
\end{lemma}
\begin{proof}
  Let~$G$ be the induced graph of~$\phi$,~$G_1$ be the induced subgraph of~$\phi_1$, and~$G_2$ the induced subgraph of~$\phi_2$. Also let~$s_1,t_1$ be the terminals of~$G_1$ and~$s_2,t_2$ the terminals of~$G_2$ as well as~$e^s_1,e^s_2,e^t_1,e^t_2$ be the legs of~$G_1$ and~$G_2$.
  The proof that~$\phi$ is rectilinear and the proof for the equations of~$b^l$ and~$b^r$ follow from the work of Didimo et al.~\cite[Lemma 5]{DIDIMO22}.

  The equality for~$s^z$ is easy to see since there exists an orthogonal representation~$\ogr$ of~$G$ with a zero-labelled path if and only if both subgraphs have orthogonal representations with a zero-labelled path.
  
  Regarding the other two step values, we only show equality for~$s^l$, as~$s^r$ follows analogously. First, we prove the ''$\geq$''-direction where we here have to show that~$s^l$ is greater than any of the three Terms~(\ref{eq:-2leg-series-value-sl1}),~(\ref{eq:-2leg-series-value-sl2}), and~(\ref{eq:-2leg-series-value-sl3}) on the right-hand side. For Term~(\ref{eq:-2leg-series-value-sl1}), we know with \cref{cor:bendbetween} that an orthogonal representation~$\ogr_1$ of~$G_1$ with~$\sigma(\ogr_1)=0$ exists. Now let~$\ogr$ be an orthogonal representation of~$G$ containing~$\ogr_1$. Then for every edge~$e$ in~$G_2$ we know that~$\lref{s}{e} = \lref{s_2}{e}$. From \cref{def:stepvalues} we see that the left step value of~$G$ is at least the left step value of~$G_2$ for such an orthogonal representation~$\ogr$. In other words~$s^l \geq s_2^l$ (Term~(\ref{eq:-2leg-series-value-sl1})). This is represented in the leftmost drawing of \cref{fig:2-leg-series-sl}.
  
  Next, assume~$b_1^l>0$ so that the Iversion bracket in Term~(\ref{eq:-2leg-series-value-sl2}) evaluates to~$1$ (see \cref{fig:2-leg-series-sl-b}). Then there exists an orthogonal representation~$\ogr_1$ of~$G_1$ with~$\sigma(\ogr_1)=-1$. As an orthogonal representation~$\ogr_2$ of~$G_2$ exists with spirality~$\sigma(\ogr_2)=b_2^r$, it follows for the orthogonal representation~$\ogr$ of~$G$ created by combining~$\ogr_1$ and~$\ogr_2$ that 
  \[\sigma(\ogr)=\lrefs{e^t}=\infoMath{\lrefs{e^s_2}}{=-1} + \infoMath{\lref{s_2}{e^t_2}}{=\sigma(\ogr_2)=b_2^r} = b_2^r-1.\] 
  In summary,~$\ogr$ contains a negatively-labelled edge, namely~$e^t_1$ in every st-path and has~$\sigma(\ogr)=b_2^r-1$.
  This implies~$s^l \geq b_2^r \cdot [b_1^l>0]$ (Term~(\ref{eq:-2leg-series-value-sl2})). 
  
  Finally, consider the case~$s_1^l > 0$ so that the Iversion bracket in Term~(\ref{eq:-2leg-series-value-sl3}) evaluates to~$1$ (see \cref{fig:2-leg-series-sl-c}). By \cref{def:stepvalues} there exists an orthogonal representation~$\ogr_1$ of~$G_1$ with~$\sigma(\ogr_1) = \lref{s_1}{e^t_1} = s_1^l-1$ that contains an edge in every st-path with a negative relative label. Now as an orthogonal representation~$\ogr_2$ of~$G_2$ with~$\sigma(\ogr_2) = b_2^r$ exists, we get by concatenating~$\ogr_1$ and~$\ogr_2$ an orthogonal representation~$\ogr$ of~$G$, containing a negatively-labelled edge in every st-path and~$\sigma(\ogr)=s^l_1 + b_2^r - 1$. This implies that~$s^l \geq (s_1^l + b_2^r)\cdot [s_1^l> 0]$ (Term~(\ref{eq:-2leg-series-value-sl3})).

  Now to the~''$\leq$''-direction. Here we have to show that in every case~$s^l$ is smaller or equal to at least one Term on the left-hand side. As every such term is non-negative, the case $s^l=0$ is trivial. So suppose~$s^l=x > 0$. Then there exists an orthogonal representation~$\ogr$ of~$G$ that contains a negatively-labelled edge in every st-path and has total spirality~$x-1$. Now let~$e=e_1^t=e_2^s$ be the edge connecting the two components~$G_1$ and~$G_2$ and~$\lrefs{e}$ be the relative label of this edge. We distinguish between two cases.
  \textbf{Case 1:}~$\lrefs{e} = y < 0$. Then this implies~$\sigma(\ogr_1)<0$ and therefore~$b_1^l > 0$. As~$\sigma(\ogr)=x-1$ we get for~Term~\ref{eq:-2leg-series-value-sl1} that
  \[b_2^r\cdot[b_1^l > 0] = b_2^r \geq \sigma(\ogr_2) = \sigma(\ogr) - \sigma(\ogr_1) = x-1-y \geq x = s^l.\]

  \textbf{Case 2:}~$\lrefs{e}=y\geq 0$. Then~$b_1^r \geq y$ and as the spirality of~$G$ is~$x-1$ it follows for~$G_2$ that~$b_2^r \geq \max(0,x-y - 1)$. Now, since an edge with a negative relative label has to be present in every st-path and~$\lrefs{e} \geq 0$. This edge must be contained in one of the two components. If it is contained in~$\ogr_1$, then~$s_1^l \geq y+1$ and Term~(\ref{eq:-2leg-series-value-sl3}) satisfies
  \[(s_1^l + b_2^r) \cdot [s_1^l > 0] \geq y + 1 + \max(0, x - y - 1) \geq x = s^l.\]
  If it is contained in~$\ogr_2$, then the following situation arises. First,~$\ogr_1$ makes at least~$y$ right turns along each st-path to achieve~$\lrefs{e}=y>0$, then~$\ogr_2$ makes~$y+1$ left turns along each st-path to the edge with the negative relative label and afterwards makes at least~$x$ right turns again to achieve~$\sigma(\ogr)=x-1$. \cref{lem:2-leg-elementarytransform} can now be applied to the first~$y$ left turns in~$\ogr_2$. This results in an orthogonal representation~$\ogr_2'$ of~$G_2$ with an edge in every st-path having relative label~$-1$ and with the~$x$ right turns afterwards the representation still has spirality~$x-1$. This implies~$s_2^l \geq x$ and Term~(\ref{eq:-2leg-series-value-sl3}) satisfies~$s_2^l \geq x =s^l$.
\end{proof}


\begin{figure}
  \centering\includegraphics[]{figures/2-leg-series-sl.pdf}
  {
    \phantomsubcaption\label{fig:2-leg-series-sl-a}  
    \phantomsubcaption\label{fig:2-leg-series-sl-b}
    \phantomsubcaption\label{fig:2-leg-series-sl-c}
  }
  \caption{An abstract view of creating a non-zero left step value~$s^l$ in a series composition of two subgraphs~$G_1$ and~$G_2$.}\label{fig:2-leg-series-sl}
\end{figure}

 To formulate a similar result for a~$\node{P}$-node, we first introduce more notation.
 \begin{definition}
  Let~$\phi$ be a~$\node{P}$-node, let~$G$ be its induced graph, and let~$G_1$,$G_2$ be the induced subgraphs of the child nodes~$\phi_1$ and~$\phi_2$. Let moreover~$e_1^s,e_1^t,e_2^s,e_2^t$ be the legs of~$G_1$ and~$G_2$. For an angle assignment~$\aas$ of~$G$ we define the \emph{rotation values}~$r^s_1=\rot(e^s,e_1^s)$,~$r^s_2=\rot(e^s,e_2^s)$,~$r^t_1=\rot(e_1^t,e^t)$, and~$r^t_2=\rot(e_2^t,e^t)$. We call the tuple~$[r^s_1,r^t_1,r^s_2,r^t_2]$ a \emph{rotation combination}.
 \end{definition}
 For an orthogonal or ortho-radial representation we know that~$r^s_1$ and~$r^t_1$ are in the set~$\{-1,0\}$ and that~$r^s_2$ and~$r^t_2$ are in the set~$\{0,1\}$. Moreover,~$r_1^s$ and~$r^s_2$ can not be~$0$ at the same time and this also holds for~$r^t_1$ and~$r^t_2$. Finally, the equations~$\rot(e^t_1,e^t_2)= |r^t_1+r^t_2| \in \{0,1\}$ and~$\rot(e^s_2,e^s_1)= |r^s_1+r^s_2| \in \{0,1\}$ hold.

\begin{lemma}\label{lem:2-leg-parallel-value}
  Let~$\phi$  be a~$\node{P}$-node not containing~$f_c$, where its children~$\phi_1$ and~$\phi_2$ both are rectilinear-plane. Also, let~$\mstructure{1}$ be the \structure{} of~$\phi_1$ as well as~$\mstructure{2}$ be the \structure{} of~$\phi_2$.
  Then~$\phi$ is rectilinear-plane if and only if
  \[b_1^r + b_2^l \geq 2.\]
  Moreover, in the case that~$\phi$ is rectilinear-plane the \structure{}~$[b^l,b^r,s^l,s^r,s^z]$ of~$\phi$ satisfies the following.
  \begin{align*}
    b^l &= \min(b_1^l+2,b_2^l) \\
    b^r &= \min(b_1^r,b_2^r+2) 
  \end{align*}
    \begin{numcases}{s^l = \max}
      [b_1^r > 0] \cdot [b_2^l > 0],\label{eq:2-leg-parallel-value-sl1}\\
      \min(b_1^r, s_2^l+1) \cdot [s_2^l > 0] \cdot [b_1^r \geq 2]\label{eq:2-leg-parallel-value-sl2}
    \end{numcases}
    \begin{numcases}{s^r = \max}
      [b_1^r > 0] \cdot [b_2^l > 0],\label{eq:2-leg-parallel-value-sr1}\\
      \min(b_2^l, s_1^r+1) \cdot [s_1^r > 0] \cdot [b_2^l \geq 2]\label{eq:2-leg-parallel-value-sr2}
    \end{numcases}
    \begin{align}
    s^z &= \max \{[b_1^r \geq 2] \cdot s_2^z, [b_2^l \geq 2] \cdot s_1^z\}\label{eq:2-leg-parallel-value-s0}
  \end{align}
\end{lemma}
\begin{proof}
  Let~$G$ be the induced graph of~$\phi$,~$G_1$ the induced subgraph of~$\phi_1$, and~$G_2$ the induced subgraph of~$\phi_2$. Also let~$s_1,t_1$ be the terminals of~$G_1$ and~$s_2,t_2$ the terminals of~$G_2$ as well as~$e^s_1,e^s_2,e^t_1,e^t_2$ be the legs of~$G_1$ and~$G_2$.
  The proof for having an orthogonal representation as well as the values of~$b^l$ and~$b^r$ follows from Didimo et al.~\cite[Lemma 7, Lemma 8]{DIDIMO22} together with \cref{cor:bendbetween}. 
  
  Regarding the two step values~$s^l$ and~$s^r$, we only show the equality for $s^l$, as~$s^r$ follows analogously, and start with the ''$\geq$''-direction. We here have to show that~$s^l$ is greater than any of the three terms on the right-hand side.
  
  \begin{figure}
    \centering\includegraphics{figures/2leg-parallel-example.pdf}
    {
     \phantomsubcaption\label{fig:2-leg-parallel-value-sl1}
     \phantomsubcaption\label{fig:2-leg-parallel-value-sl2}
     \phantomsubcaption\label{fig:2-leg-parallel-value-s0}
     }
    \caption{Examples of how a parallel connection of subgraphs~$G_1$ and~$G_2$ result in~$s^l=1$ for the left step value~$(a)$, in~$s^l=2$ for the left step value~$(b)$, and in~$s^z=1$ for the zero step value~$(c)$.}\label{fig:2-leg-parallel-values}
  \end{figure}

  As a start, consider Term~(\ref{eq:2-leg-parallel-value-sl1}). Unless both Iversion brackets in Term~(\ref{eq:2-leg-parallel-value-sl1}) result in a value of~$1$, the total term is~$0$ and~$s^l \geq 0$ trivially holds. Therefore, suppose both~$b_1^r>0$ and~$b_2^l>0$, which implies~$[b_1^r > 0] \cdot [b_2^l > 0] = 1$. Then there exist orthogonal representations~$\ogr_1$ of~$G_1$ with~$\sigma(\ogr_1)=1$ and~$\ogr_2$ of~$G_2$ with~$\sigma(\ogr_2)=-1$. Using the rotation combination~$[r^s_1,r^t_1,r^s_2,r^t_2]=[-1,0,0,1]$ results in an orthogonal representation~$\ogr$ of~$G$ as also seen in \cref{fig:2-leg-parallel-value-sl1}. It then follows that~$\lrefs{e_1^s}=\lrefs{e_2^t}=-1$ and therefore~$s^l\geq 1$.
  
  Now consider Term~(\ref{eq:2-leg-parallel-value-sl2}). Again, unless both conditions in the Iversion brackets are true,~$s^l \geq 0$ trivially holds.
  Therefore, suppose~$s_2^l > 0$ and~$b_1^r \geq 2$ and let~$b=\min(b_1^r-2, s_2^l-1)$. Then there exists an orthogonal representation~$\ogr_1$ of~$G_1$ with~$\sigma(\ogr_1)=b+2$, and an orthogonal representation~$\ogr_2$ of~$G_2$ with~$\sigma(\ogr_2)=b$ containing a negatively-labelled edge in every~st-path of~$G_2$. By connecting~$\ogr_1$ and~$\ogr_2$ using the rotation combination~$[r^s_1,r^t_1,r^s_2,r^t_2]=[-1,0,0,1]$ we get an orthogonal representation~$H$ of~$G$, as the newly created face~$f$ has the rotation 
  \[\rot(f)=\rot(e_2^s,e_1^s) + \sigma(\ogr_1) - \sigma(\ogr_2) + \rot(e_1^t,e_2^t) = 1 + b +2  - b + 1 =4.\]
  The case~$s_2^l=1$ and~$b_1^r=2$ is shown in \cref{fig:2-leg-parallel-value-sl2}. Every st-path has to either traverse~$G_1$ or~$G_2$. Traversing~$G_1$, it contains the edge~$e^s_1$ with~$\lrefs{e_1^s}=r_1^s=-1$. Traversing~$G_2$ it contains with~$\lrefs{e_2^s}=r_2^s=0$ a negatively-labelled edge as by construction. The orthogonal representation~$\ogr$ has spirality 
  \[\sigma(H)=\lrefs{e^t} = r_1^s + \sigma(\ogr_1) +r_1^t = -1 + b + 2 + 0 = b+1 = \min(b_1^r-1, s_2^l).\]
  With \cref{def:stepvalues}, this implies~$s^l \geq \min(b_1^r, s_2^l+1) \cdot [s_2^l > 0] \cdot [b_1^r \geq 2]$.

  Now to the ''$\leq$''-direction. We here have to show that for every orthogonal representation of~$G$,~$s^l$ is smaller or equal to at least one term inside the maximum on the left-hand side. As every such term must be non-negative, the case~$s^l=0$ is trivial. Therefore, suppose~$s^l =x > 0$.
  Then there exists an orthogonal representation~$\ogr$ of~$G$ with~$\sigma(\ogr)=\lrefs{e^t}=x-1$ and with an edge having a negative relative label in every st-path. Let~$\ogr_1$ be the induced orthogonal representation of~$G_1$ and~$\ogr_2$ be the induced orthogonal representation of~$G_2$. The fact~$\lrefs{e^t}=x-1$ implies the following.
  \begin{align}
    &\sigma(\ogr_1) = \lref{s_1}{e^t_1}\nonumber\\
    & = \infoMath{r_1^s + \lref{s_1}{e^t_1} + r_1^t}{=\lrefs{e^t}=x-1} \infoMath{-r_1^s - r_1^t}{\in \{0,2\}} \in \{x-1,x+1\} \label{eq:2-leg-parralel-values-sigma1}\\
    &\sigma(\ogr_2) = \lref{s_2}{e^t_2}\nonumber \\
    & = \infoMath{r_2^s + \lref{s_2}{e^t_2} + r_2^t}{=\lrefs{e^t}=x-1}  \infoMath{-r_2^s- r_2^t}{\in \{-2,0\}} \in \{x - 3,x-1\} \label{eq:2-leg-parralel-values-sigma2}
  \end{align}
  
  The fact~$s^l = x > 0$ implies that in every st-path a negatively-labelled edge has to be present, and particularly in every st-path traversing~$G_2$. The negatively-labelled edge can not be in the set~$\{ e^s,e^t,e^s_2,e^t_2\}$ because 
~$\lrefs{e^s} = 0$,~$\lrefs{e^t} = x-1 \geq 0$,~$\lrefs{e^s_2} =r_2^s\geq 0$, and
  \begin{align}
    \lrefs{e^t_2} = \infoMath{\lrefs{e^t_2} + r_2^t}{= \lrefs{e^t}=x-1 > 0} - r_2^t \geq 0.
  \end{align}
  Therefore, a negatively-labelled edge must be present in every path from~$s_2$ to~$t_2$ inside~$\ogr_2$.
  We now make a case distinction.
  
  \textbf{Case 1:}~$s^l=x=1$. Here we show that Term~(\ref{eq:2-leg-parallel-value-sl1}) must also be~$1$. For a proof by contradiction assume~$b_1^r=0$ or~$b_2^l=0$, which would result in the Term~(\ref{eq:2-leg-parallel-value-sl1}) being~$0$ and not~$1$. Having~$b_2^l=0$ implies~$\sigma(\ogr_2)\geq 0$ and combining this with \cref{eq:2-leg-parralel-values-sigma2},~$\sigma(\ogr_2)=0$ follows. And as~$\ogr_2$ contains a negatively-labelled edge in every path from~$s_2$ to~$t_2$ inside~$\ogr_2$ we know that~$s_2^l>0$. But with \cref{lem:2-leg-brgreatersl} this would imply~$b_2^l>0$ and a contradiction is formed. The same argumentation holds if~$b_1^r=0$ in combination with \cref{eq:2-leg-parralel-values-sigma1}.

  \textbf{Case 2:}~$s^l = x \geq 2$. 
  Not both~$r_1^s$ and~$r_2^s$ can be~$0$ at the same time. This implies that either \cref{eq:2-leg-parralel-values-sigma1} or \cref{eq:2-leg-parralel-values-sigma2} has a stronger bound. More specifically, either~$\sigma(\ogr_1) = x-1 + 1 - r_1^t \geq x > 0$ or~$\sigma(\ogr_2)=x-1 -1 -r_2^t \geq x-2 \geq 0$ holds. Using both equations we can, with the knowledge that~$G_2$ contains an edge with a negative relative label, show for Term~(\ref{eq:2-leg-parallel-value-sl1}) that 
  \[s^l = x \leq \min(\sigma(\ogr_1),\sigma(\ogr_2)+2) \leq\min(b_1^r, s_2^l+1).\] 
  
  We now have shown that for an arbitrary orthogonal representation~$\ogr$ of~$G$ the left step value~$s^l$ is always smaller than either Term~(\ref{eq:2-leg-parallel-value-sl1}) or Term~(\ref{eq:2-leg-parallel-value-sl2}) and equality follows for~$s^l$.
  
  What is left is the equality proof for~$s^z$. For the ''$\geq$''-direction, suppose that~$s_1^z=1$ and~$b_2^l \geq 2$. Then there exist an orthogonal representation~$\ogr_1$ of~$G_1$ with an st-path~$P_1$ having only relative label~$0$ and an orthogonal representation~$\ogr_2$ of~$G_2$ with~$\sigma(\ogr_2)=-2$. A rotation combination of~$[r^s_1,r^t_1,r^s_2,r^t_2]=[0,0,1,1]$ results in a combined orthogonal representation~$\ogr$ of~$G$ as also seen in \cref{fig:2-leg-parallel-value-s0}. The path~$P=e_1^s + P_1 + e_1^t$ contains with~$r_1^s=r_1^t=0$ only edges with relative label~$0$ and~$s^z=1$ follows. The same holds true for the other case of Term~(\ref{eq:2-leg-parallel-value-s0}) and the rotation combination~$[r^s_1,r^t_1,r^s_2,r^t_2]=[-1,-1,0,0]$. For the ''$\leq$''-direction suppose~$s^z=1$. Then there exists an orthogonal representation~$\ogr$ of~$G$ containing an st-path with only zero-labelled edges. This path has to traverse either~$G_1$ or~$G_2$. Without loss of generality, let~$G_1$ contain this path, which implies~$s_1^z = 1$ as well as~$r_1^s=r_1^t=0$. Then~$r_2^s=r_2^t= 1$ must hold and using the same argumentation as in \cref{eq:2-leg-parralel-values-sigma2},~$\sigma(\ogr_2) = -2$ and~$b_2^l\geq2$ follows, which then implies for Term~(\ref{eq:2-leg-parallel-value-s0}) that
  \[\max \{[b_1^r \geq 2] \cdot s_2^z, [b_2^l \geq 2] \cdot s_1^z\} \geq [b_2^l \geq 2] \cdot s_1^z = 1 = s^z.\]
\end{proof}

Until now, we have only looked at tree nodes not containing the central face~$f_c$, and tried to find ways to calculate step values. These step values are now used to create~$f_c$ at the marked parallel node in the decomposition tree. We start with restricting the possible combinations of step values for a 2-legged SP-graph.

\begin{lemma}\label{lem:2-leg-nolonelystep}
  There does not exist a \twlegrecplsptg{} with
  \[[s^l, s^r, s^z] \in \{[0, x, 0],[x ,0 ,0]\}\]
  for any~$x \in \mn_0$.
\end{lemma}
\begin{proof}
  Only the proof for~$[s^l,s^r,s^z] \not\in [x,0,0]$ is given, since the other case follows analogously. To form a contradiction, assume a \twlegrecplsptg{}~$G$ exists with step values~$[x,0,0],\ x \in \mn_0$. As both~$\node{Q}$- and~$\node{D}$-nodes have step values~$[0,0,1]$,~$G$ has to be the result of some composition of two subgraphs~$G_1$ and~$G_2$. Let~$\mstructure{1}$ be the \structure{} of~$G_1$ and~$\mstructure{2}$ be the \structure{} of~$G_2$. 
  We now show that for $G$ to have the step values $[x,0,0]$, at least one of the subgraphs must have the step values $[y,0,0]$ or $[0,y,0]$ for $y\in \mn$. This implies that $G$ would have to be the result of an infinite composition chain. Therefore, such a~$G$ does not exist.

  \textbf{Case 1:}~$G$ is the result of a parallel composition of~$G_1$ and~$G_2$. As~$s^r=0$, both Term~(\ref{eq:2-leg-parallel-value-sl1}) and Term~(\ref{eq:2-leg-parallel-value-sl2}) in \cref{lem:2-leg-parallel-value} have to be~$0$. With~$b_2^l\geq s_2^l$ (\cref{lem:2-leg-brgreatersl}) this implies either~$b_1^r = 0$ or~$b_2^l=0$. But for~$G$ to be rectilinear-plane, \cref{lem:2-leg-parallel-value} also states that~$b_1^r + b_2^l \geq2$. Therefore, one of the two bend values must be~$0$ and the other one greater or equal to~$2$. Without loss of generality, let~$b_1^r\geq 2$ and~$b_2^l=0$. With the inequality~$b_2^l\geq s_2^l$ we also get~$s_2^l=0$. Moreover, with~$b_1^r \geq 2$ and~$s^z=0$, \cref{eq:2-leg-parallel-value-s0} implies that~$s_2^z=0$ as well. Therefore, the step values of~$G_2$ must be of the form~$[0,y,0]$ for some~$y \in \mn_0$.

  \textbf{Case 2:}~$G$ is the result of a series composition of~$G_1$ and~$G_2$. Then \cref{lem:2-leg-series-value} restricts the step values of the children such that
  \begin{align*}
    &(s_1^r = 0 \land s_2^r  = 0) &\text{Terms~(\ref{eq:-2leg-series-value-sr1}) and~(\ref{eq:-2leg-series-value-sr3})}\\
    \land\ &( s_1^z = 0 \lor s_2^z = 0) & \text{\cref{eq:-2leg-series-value-s0}}
\end{align*}
  This implies that for at least one child the step values must be of the form~$[y,0,0]$ for some~$y \in \mn_0$.
\end{proof}



%\begin{lemma}\label{lem:2-leg-nobendinjustonedirection}
%  There does not exist a 2-legged SP Graph with a bend value of~$1$ in one direction but zero bends in the other. Meaning that~$b^l=1$ implies~$b^r \geq 0$ and~$b^r=1$ implies~$b^l \geq 0$
%\end{lemma}
%\begin{proof}
%  Assume a 2-legged SP Graph~$G$ with~$b^l = 1$ and~$b^r=0$ exists. As both the~$\node{Q}$- and~$\node{D}$-node do not have this property,~$G$ has to be the result of some composition. \textbf{Case 1:}~$G$ is the result of a parallel composition. Then we know
%  from \cref{lem:2-leg-parallel-value} that
%  \begin{align*}
%    1 = b^l &= \min(b_1^l+2,b_2^l) \\
%    0 = b^r &= \min(b_1^r,b_2^r+2) \\
%    2 & \leq b_1^r + b_2^l
%  \end{align*}
%  which immediately contradicts itself. \textbf{Case 1:}~$G$ is the result of a series composition. From \cref{lem:2-leg-series-value} we then know that
%  \begin{align*}
%    1 = b^l &= b_1^l + b_2^l \\
%    0 = b^r &= b_1^r + b_2^r \\
%  \end{align*}
%  which implies that either~$b_1^l>1 \land b_1^r = 0$ or~$b_2^l>0 \land b_2^r=0$.  We now have shown that if a~$G$ with the assumed bend values exists, it has to be the result of an infinite composition chain. Therefore such a~$G$ does not exist.
%\end{proof}
\begin{figure}
  \centering
  \includegraphics[]{figures/2-leg-f0-example.pdf}

\caption{On the left, two 2-legged SP-graphs and on the right their parallel composition surrounding~$f_c$. The arrows indicating the direction of st-paths in the orthogonal drawings point in different directions in the ortho-radial one.}\label{fig:2-leg-f0-example}
\end{figure}

The following lemma shows that for 2-legged series-parallel 3-graphs an edge always has the same label, no matter in which essential cycle, as long as we consider an orientation of the edge.

\begin{figure}
  \centering\includegraphics{figures/sp3-label-independent-of-cycle.pdf}
  \caption{A representation of the cyclic chain of subgraphs including the cycles~$C$ and~$C'$ from \cref{lem:label-indipendent-of-cycle}. The cycles share a common edge~$e$ in the subgraph~$G^e$ and enter it via the common leg~$l_e$. The two possible locations of~$e^*$ are both represented here. It may either be contained in the subgraph~$G^*$ contained in the cyclic chain or be outside the chain (and therefore closer to~$f_c$) and connected to it at a terminal~$t$.}\label{fig:label-indipendent-of-cycle}
\end{figure}

\begin{lemma}\label{lem:label-indipendent-of-cycle}
  Let~$(G,\emb)$ be a 2-legged series-parallel plane 3-graph that admits a (possibly invalid) ortho-radial representation~$\orr$ with a reference edge~$e^*$ and let~$C$ and~$C'$ be two simple essential cycles sharing the same oriented edge~$\de{e}$. Then~$\lbl_C(\de{e})=\lbl_{C'}(\de{e})$.
\end{lemma}
\begin{proof}
  Let~$\mathcal{G}$ be the set of inclusion-wise maximal 2-legged series-parallel subgraphs of~$G$, where their induced representations are orthogonal. Both cycles~$C$ and~$C'$ can not be totally contained in a single subgraph of~$\mathcal{G}$ since they are essential cycles and can therefore only be contained in an ortho-radial representation. As the union of the subgraphs in~$\mathcal{G}$ is the whole graph~$G$, both cycles must traverse a cyclic chain of subgraphs in~$\mathcal{G}$ instead. And as both cycles must traverse the subgraph~$G_e\in \mathcal{G}$ containing~$e$, they must traverse the same cyclic chain we call~$\mathcal{S}$. Otherwise, some subgraph in~$\mathcal{G}$ is either not inclusion-wise maximal or its induced representation would be an ortho-radial one. For the cycles to be simple and both traverse the same oriented edge~$\de{e} \in G_e$, they must traverse~$G_e$, and therefore every subgraph in~$\mathcal{S}$, also in the same direction. See \cref{fig:label-indipendent-of-cycle} for an illustration.

  There are two cases based on the location of~$e^*$. If~$e^*$ is contained in a subgraph we call~$G^*\in\mathcal{S}$, then let~$l^*$ be the leg of~$G^*$ over which both cycles leave this subgraph. There must exist a reference path from~$e^*$ to~$l^*$ such that this reference path respects both~$C$ and~$C'$. This implies~$\lbl_C(l^*)=\lbl_C'(l^*)$. If~$e^*$ is not contained in a subgraph in~$\mathcal{S}$, there exists some leg~$l^*$ of a subgraph in~$\mathcal{S}$ with a reference path from~$e^*$ to~$l^*$ only entering the cyclic chain at~$l^*$. Then this reference path respects~$C$ and~$C'$, and again it follows that~$\lbl_C(l^*)=\lbl_{C'}(l^*)$.

  Knowing that a single leg in the cyclic chain has the same label, it follows with \cref{lem:2-legged-rellabel-welldefined} that every leg of every subgraph in~$\mathcal{S}$ has the same label. Let~$l_e$ be the leg of~$G_e$ over which~$C$ and~$C'$ enter~$G_e$. Again \cref{lem:2-legged-rellabel-welldefined} implies that~$\rot(C[l_e,e])=\rot(C'[l_e,e])$ and with~$\lbl_C(l_e)=\lbl_C'(l_e)$ it follows that~$\lbl_C(e)=\lbl_C(l_e)+\rot(C[l_e,e])=\lbl_C'(l_e)+\rot(C'[l_e,e])=\lbl_C'(e)$.
\end{proof}

With \cref{lem:label-indipendent-of-cycle} we now write~$\lbl(\de{e})$ instead of~$\lbl_C(e)$ if the oriented edge~$\de{e}$ is contained in~$C$. We can even define a label for oriented edges that currently are not contained in any essential cycle, as once they are, the labels would be equal. To make it clear in which way an oriented edge is directed, we use the following notation. We use~$\de{e}$ to represent the orientation of~$e$ as it occurs in an st-path of~$G$, and we use~$\rde{e}$ to represent the reversed orientation of~$\de{e}$. We use the notation~$\reversegraph{G}$ for the reversed 2-legged SP-graph of~$G$ where the terminals~$s$ and~$t$ are flipped. If~$\de{e} \in G$, then~$\rde{e} \in \reversegraph{G}$.

We are now ready to create the central face at some~$\node{P}$-node in the recursion. To get a feeling for what this means, \cref{fig:2-leg-f0-example} shows an example drawing of two children and their parallel composition around the center. As the embedding is fixed, the left subgraph~$G_1$ wraps clockwise while the right subgraph~$G_2$ wraps counterclockwise around the circle. Therefore, a left bend in~$G_1$ and a right bend in~$G_2$ may both point radially outwards.

\begin{definition}\label{def:2-leg-st-upwards}
  Let~$(G,\emb)$ be a \twlegrecplsptg{} and let~$\orr$ be a valid ortho-radial representation of~$G$. Then~$\orr$ is called \emph{st-outwards} if the legs of~$G$ point radially outwards.
\end{definition}

\begin{lemma}\label{thm:2-legged-f0-always-upwards}
  Let~$\phi$ be a marked~$\node{P}$-node at which the face~$f_0$ should be created and where its children~$\phi_1$ and~$\phi_2$ both are rectilinear-plane. If~$\mstructure{1}$ is the \structure{} of~$\phi_1$ and~$\mstructure{2}$ is the \structure{} of~$\phi_2$, then there exists a valid ortho-radial representation of~$\phi$ if and only if any of the following equations hold.
  \begin{align}
    s_1^z=s_2^z = 1 \label{eq:2-legged-f0-always-upwards__step_values}\\
     b_1^l ,s_2^r \geq 1\lor b_2^r ,  s_1^l  \geq 1\label{eq:2-legged-f0-always-upwards__bend_limitations^z}\\
    b_1^l \geq 2\lor b_2^r \geq 2 \label{eq:2-legged-f0-always-upwards__bend_limitations_2}
  \end{align}
Moreover, if~$G$ admits any valid ortho-radial representation, then it also admits an~st-outwards one.
\end{lemma}
\begin{proof}
  Let~$G$ be the induced graph of~$\phi$,~$G_1$ be the induced subgraph of~$\phi_1$, and~$G_2$ be the induced subgraph of~$\phi_2$. Also let~$s_1,t_1$ be the terminals of~$G_1$ and~$s_2,t_2$ the terminals of~$G_2$ as well as~$e^s_1,e^s_2,e^t_1,e^t_2$ be the legs of~$G_1$ and~$G_2$.

  First, we prove the equivalence for the existence of a valid ortho-radial representation and then that there always exists one that is~st-outwards. For the ''$\impliedby$''-direction we make a case distinction.

  \textbf{Case 1:} \cref{eq:2-legged-f0-always-upwards__step_values} holds. We then know that~$s_1^z= s_2^z=1$. Therefore, orthogonal representations~$\ogr_1$ of~$G_1$ and~$\ogr_2$ of~$G_2$ exist with~$\sigma(\ogr_1)=\sigma(\ogr_2)=0$ and both with an st-path having only relative label $0$. Now let~$\orr$ be the representation of~$G$ obtained by combining~$\ogr_1$ and~$\ogr_2$ with rotation combination~$[r_1^s,r_1^t,r_2^s,r_2^t]=[-1,-1,1,1]$. See \cref{fig:2-leg-fc-value-s0} for an example of how the complete ortho-radial representation gets connected. For the new central and outer face it follows that
  \[\rot(f_c) = \rot(f_o)= \infoMath{\lref{s_1}{e^t_1}}{=\sigma(\ogr_1)=0} + \infoMath{\rot(e^t_1, e^t_2)}{=0} - \infoMath{\lref{s_2}{e^t_2}}{=\sigma(\ogr_2)=0} + \infoMath{\rot(e^s_2,e^s_1)}{=0} = 0,\]
  and~$\orr$ is an ortho-radial representation. Now use~$\de{e^s_1}$ as the reference edge in~$\orr$.  We then know that $\lbl_C(e)=\lbl(\de{e})=\lref{s_1}{e}$ for an edge~$e \in G_1$. For an edge $e \in G_2$, let $P$ be a path from $e_2^s$ to the starting vertex of $\de{e}$. It then holds that 
  \[\lbl_C(e)=\lbl(\rde{e})=\dir(\de{e^s_1},P,\rde{e})=\rot(\rde{e_1^s} + P)=\infoMath{-\rot(e_2^s,e_1^s)}{=0} + \lref{s_2}{e}=\lref{s_2}{e}.\]
  Let~$C$ be an arbitrary simple essential cycle in~$\orr$ and let~$P_1$ be the traversed path in~$G_1$ and~$P_2$ the traversed path in~$G_2$. Then $P_2$ is an st-path of the reverse graph~$\reversegraph{G_2}$.
  By \cref{def:stepvalues,lem:2leg-s^z-other-paths} both~$P_1$ and~$P_2$ contain either only zero-labelled edges relative to~$e^s_1$ and~$e^s_2$ or at least one path contains both a positively- and a negatively-labelled edge relative to their starting leg. As these relative labels directly translate to labels of~$C$, it follows that~$C$ either only contains zero-labelled edges or at least one positively- and one negatively-labelled edge.
  
  \textbf{Case 2:} \cref{eq:2-legged-f0-always-upwards__bend_limitations^z} holds. Due to being analogous, we only discuss the first case where~$b_1^l\geq 1$ and~$s_2^r > 0$. There must exist an orthogonal representation~$\ogr_1$ of~$G_1$ with~$\sigma(\ogr_1)=-1$ and an orthogonal representation~$\ogr_2$ of~$G_2$ with~$\sigma(\ogr_2)=0$ containing an edge in every st-path with a positive relative label. Let~$\orr$ be the combined representation of~$\ogr_1$ and~$\ogr_2$ with rotation combination~$[r_1^s,r_1^t,r_2^s,r_2^t]=[-1,0,1,1]$ as shown in \cref{fig:2-leg-fc-value-b1}. Then
  \[\rot(f_c) = \rot(f_o) = \infoMath{\lref{s_1}{e^t_1}}{=\sigma(\ogr_1)=-1} + \infoMath{\rot(e^t_1, e^t_2)}{=1} - \infoMath{\lref{s_2}{e^t_2}}{=\sigma(\ogr_2)=0} + \infoMath{\rot(e^s_2,e^s_1)}{=0} = 0.\]
  Therefore,~$\orr$ is an ortho-radial representation. We again use~$\de{e^s_1}$ as the reference edge in~$\orr$ and the same connection between relative and normal labels as in Case 1 holds. Let~$C$ be an arbitrary simple essential cycle in~$\orr$,~$P_1$ the path through~$G_1$, and~$P_2$ the path through~$G_2$.
  As~$e^t_1$ is a leg of~$G_1$, we know that it must be part of~$P_1$ and~$\lbl_C(e^t_1)=\lref{s_1}{e^t_1} = \sigma(\ogr_1)=-1$. By the construction of~$\ogr_2$  we also know that~$P_2$ contains an edge~$e_2$ with~$\lbl_C(e_2)=\lref{s_2}{e_2}>0$. So~$C$ is valid and therefore also~$\orr$ is valid.


  \begin{figure}
       \centering\includegraphics{figures/2leg-par-fc-s0.pdf}
       \caption{Two subgraphs~$G_1$ and~$G_2$, both with $s^z=1$, forming a valid ortho-radial representation based only on step values. The highlighted edge~$e^*$ is the reference edge.Both subgraphs have~$s^z=1$.}\label{fig:2-leg-fc-value-s0}
   \end{figure}
   \begin{figure}
     \begin{subfigure}[b]{0.49\textwidth}
       \centering
       \includegraphics{figures/2leg-par-fc-b1.pdf}
       \caption{Subgraph~$G_1$ has~$b_1^l>0$ and~$G_2$ has~$s_2^r>0$.}\label{fig:2-leg-fc-value-b1}
     \end{subfigure}
     \hfill
     \begin{subfigure}[b]{0.49\textwidth}
       \centering
       \includegraphics{figures/2leg-par-fc-b2.pdf}
       \caption{Subgraph~$G_1$ has~$b_2^l\geq 2$.}\label{fig:2-leg-fc-value-b2}
     \end{subfigure}
     \caption{Two subgraphs~$G_1$ and~$G_2$ forming a valid ortho-radial representation based both on bend and step values. The highlighted edge~$e^*$ is the reference edge.}
   \end{figure}


  \textbf{Case 3:} \cref{eq:2-legged-f0-always-upwards__bend_limitations_2} holds. We again only discuss the case~$b_1^l \geq 2$. Then there exists an orthogonal representation~$\ogr_1$ of~$G_1$ with~$\sigma(\ogr_1)=-2$ as well as some orthogonal representation~$\ogr_2$ of~$G_2$ with~$\sigma(\ogr_2)=0$. Let~$\orr$ be the representation of~$G$ when combining~$\ogr_1$ and~$\ogr_2$ with the rotation combination~$[r_1^s,r_1^t,r_2^s,r_2^t]=[0,0,1,1]$ as shown in \cref{fig:2-leg-fc-value-b2}. It follows that
  \[\rot(f_c) = \rot(f_o) = \infoMath{\lref{s_1}{e^t_1}}{=\sigma(\ogr_1)=-2} + \infoMath{\rot(e^t_1, e^t_2)}{=1} - \infoMath{\lref{s_2}{e^t_2}}{=\sigma(\ogr_2)=0} + \infoMath{\rot(e^s_2,e^s_1)}{=1} = 0.\]
  Use~$\rde{e^s_2}$ as the reference edge. Let~$C$ be an arbitrary simple essential cycle in~$\orr$ and~$P_1$ be the path taken through~$G_1$. From the used rotation combination we know that~$\rot(e^s_2,e^s_1)=1$, and this implies~$\lbl_C(e^s_1)= \rot(e^s_2, e^s_1) = 1$ and~$\lbl_C(e^t_1) = \rot(e^s_2, e^s_1) + \infoMath{\lref{s_1}{e^t_1}}{=-2}= -1$.
  Therefore,~$C$ already contains a positively- and negatively-labelled edge in its path through~$G_1$ and~$\orr$ must be valid.

  Regarding the ''$\implies$''-direction, we use a proof by contradiction. So assume all equations do not hold, but there exists a valid ortho-radial representation~$\ogr$ of~$G$ with reference edge~$e^*$. Let~$\ogr_1$ be the induced orthogonal representation of~$G_1$ and~$\ogr_2$ the induced orthogonal representation of~$G_2$. Due to \cref{eq:2-legged-f0-always-upwards__step_values} not being fulfilled, we know that $s^z=0$ for at least one subgraph. With \cref{eq:2-legged-f0-always-upwards__bend_limitations^z} not being fulfilled and \cref{lem:2-leg-b0-implies-s0}, the same holds for $s^l$ and $s^r$. Using \cref{lem:2-leg-nolonelystep}, there only exist two possible situations where this is given. Either~$\mstructureSteps{1}=[0,0,1]$ and~$\mstructureSteps{2}=[x,y,0],\ x,y\in \mn$ or the inverse assignment. We only prove the case where~$\mstructureSteps{1}=[0,0,1]$, since the other case follows analogously. From~$s_2^r>0$ and \cref{eq:2-legged-f0-always-upwards__bend_limitations^z} not being fulfilled, it follows that~$b_1^l=0$ and therefore~$\sigma(\ogr_1) \geq 0$. We can calculate the spirality of~$\ogr_2$ based on the spirality of~$\ogr_1$ and~$\rot(f_c)=0$ to be
  \begin{align}
  &\sigma(\ogr_2) \nonumber\\
  =&\infoMath{\sigma(\ogr_2) + \rot(e^t_2,e^t_1) - \sigma(\ogr_1) + \rot(e^s_1,e^s_2)}{=-\rot(f_c)=0} - \infoMath{\rot(e^t_2,e^t_1)}{\in \{-1,0\}} + \infoMath{\sigma(\ogr_1)}{ \geq 0} - \infoMath{\rot(e^t_2,e^t_1)}{\in \{-1,0\}}\nonumber\\
   \geq& \sigma(\ogr_1). \label{eq:2-leg-fc-sph2geq0}
  \end{align}
  To form a contradiction, we differentiate between the concrete value of~$\sigma(\ogr_1)$ and show for each case that~$b_2^r\geq2$ in \cref{eq:2-legged-f0-always-upwards__bend_limitations_2} would hold.

  \textbf{Case 1:}~$\sigma(\ogr_1)\geq 2$. Then \cref{eq:2-leg-fc-sph2geq0} directly implies~$\sigma(\ogr_2) \geq 2$.
  
  \textbf{Case 2:}~$\sigma(\ogr_1)=0$. As~$[s_1^l,s_1^r,s_1^z] = [0,0,1]$ we know that~$\ogr_1\notin {\Omega_+(G_1,\emb_1)}, {\Omega_-(G_1,\emb_1)}$ with $\emb_1$ being the induced embedding of~$G_1$. Therefore, \cref{lem:oneofslsrs0} implies that~$\ogr_1 \in {\Omega_z(G_1,\emb_1)}$. So there exists an st-path~$P_1$ through~$G_1$ with only zero labels relative to~$e^s_1$. Therefore, in any simple essential cycle~$C$ containing~$P_1$ we know that all edges of~$P_1$ have the same, but maybe non-zero, normal label~$x$. With~$\rot(e^t_1,e^t_2) \geq 0$ we know that~$\lbl_C(e^t_2)=x$ as well. No matter the value of~$x$ it follows with~$s_2^z=0$ that~$C$ must contain a positively- and negatively-labelled edge inside the path taken through~$\ogr_2$ for~$C$ to be valid. As~$C$ was arbitrary, every st-path in~$\ogr_2$ must contain a positive and negative label. \cref{eq:2-leg-fc-sph2geq0} implies~$\sigma(\ogr_2)\geq 0$, and the same argumentation as in \cref{lem:2-leg-bgeq2IfBothPosAndNeg} (only swapping relative labels with normal labels) implies that~$b_2^r\geq 2$.

  \textbf{Case 3:}~$\sigma(\ogr_1)=1$. At first, we bound the relative labels in two special st-paths of~$G_1$. As~$s_1^l=0$, there must exist an st-path through~$G_1$ without a negative relative label. We call this special path~$S$.

  Now assume that in every st-path of~$G_1$ an edge~$e$ exists with~$\lrefs{e}\geq 2$. Then between~$s$ and every such~$e$ there must exist adjacent vertices~$u,v,w$ in the current st-path with~$\rot(uv,vw)=1$. \cref{lem:2-leg-elementarytransform} then implies the existence of another orthogonal representation~$\ogr_1'$ of~$G_1$ with~$\sigma(\ogr_1') = 1-1=0$. But as every st-path only contains one vertex with a different rotation in~$\ogr_1'$, the relative label of the edge~$e$ in each st-path is only reduced by~$1$ and therefore still positive. By \cref{def:stepvalues}, this would imply~$s_1^r>0$, which stands in contradiction to~$\mstructureSteps{1}=[0,0,1]$. Therefore, there must exist an st-path in~$G_1$, where every edge has at most a relative label of~$1$. We call this special st-path~$T$. With~$z \defeq \lbl(\de{e^s_1})$ it follows that
  \begin{align*}
    \lbl(\de{e}) \geq z,\ \forall e \in S \\
    \lbl(\de{e}) \leq z + 1,\ \forall e \in T
  \end{align*}
  Now given an arbitrary value~$z$, observe that either~$S$ or~$T$ can not contain negatively- as well as positively-labelled edges at the same time. Moreover, as~$\sigma(\ogr_1)=1$, both paths can also not contain only zero-labelled edges. Using this knowledge, we show that every st-path in the second graph~$G_2$ must contain both a positively- and a negatively-labelled edge. With the same argumentation as in \cref{lem:2-leg-bgeq2IfBothPosAndNeg} (only swapping relative labels with normal labels) this implies that~$b_2^r\geq 2$ and the ''$\impliedby$''-direction will be shown. This is done separately for the following two cases.
  
  \textbf{Case 3a:} $z \geq 0$. Then both~$S$ and~$T$ contain positively-labelled edges, but~$S$ does not contain a negatively-labelled edge. Let~$P_2$ be an arbitrary st-path in~$G_2$. Then~$S + P_2$ forms a simple essential cycle and for this cycle to be valid,~$P_2$ must contain a negatively-labelled edge. For the edge $e^t_2 \in P_2$, we also know that
  \[\lbl_C(e^t_2) = \lbl_C(e_1^t) +\rot(e_1^t,e_2^t) \geq \lbl_C(e^t_1) = \infoMath{\lbl_C(e^s_1)}{=z\geq 0} + \infoMath{\lref{e^s_1}{e^t_1}}{=1} \geq 1.\]
  Therefore,~$P_2$ also contains the positively-labelled edge~$e^t_2$. As~$P_2$ was arbitrary, every st-path of~$G_2$ contains a positively- and a negatively-labelled edge.
  
  \textbf{Case 3b:} $z<0$. Then both~$S$ and~$T$ contain negatively-labelled edges, but~$T$ does not contain a positively-labelled edge. Let~$P_2$ be an arbitrary st-path in~$G_2$. Then~$T + P_2$ forms a simple essential cycle and for this cycle to be valid,~$P_2$ must contain a negatively-labelled edge. For the edge $e^s_2 \in P_2$ we also know that
  \[\lbl_C(e^s_2) \leq \lbl_C(e^s_1) = z < 0.\]
  Therefore,~$P_2$ also contains the negative edge~$e^s_2$ and as~$P_2$ was arbitrary every st-path of~$G_2$ must contain a negatively- and a positively-labelled edge.
  
  Finally, we would have to show that if a valid ortho-radial representation exists, then there also exists one which is st-outwards. But if such a representation exists, the ''$\implies$''-direction implies that one of \cref{eq:2-legged-f0-always-upwards__step_values,eq:2-legged-f0-always-upwards__bend_limitations^z,eq:2-legged-f0-always-upwards__bend_limitations_2} holds. And due to the ''$\impliedby$''-direction already constructing an~st-outwards representation in any case, this fact is already proven.
\end{proof}


After creating the initial valid ortho-radial representation around the central face, extending the representation is trivial as the following lemma shows.
\begin{figure}
  \centering
  \includegraphics[]{figures/2-leg-fc-series.pdf}

\caption{A series composition and a parallel composition of two subgraphs~$G_1$ and~$G_2$, where~$G_1$ already contains the central face.~$G_1$ is st-outwards and~$G_2$ has no specific properties.}\label{fig:2-leg-fc-after}
\end{figure}

\begin{lemma}\label{cor:2-leg-series-after-fc}
  Let~$\phi$ be an inner node where one of its children contains~$f_c$ and is ortho-linear plane while the other child-node is rectilinear-plane. Then a valid ortho-radial representation of~$\phi$ exists that is also~st-outwards.
\end{lemma}
\begin{proof}
  Let~$\phi_1$ and~$\phi_2$ be the child nodes of~$\phi$ and without loss of generality let~$\phi_1$ be the node still containing~$f_c$. We make a proof by induction over the depth~$n$ of the marked~$\node{P}$-node in the subtree rooted at the child~$\phi_1$. For the base case~$n=1$ we know that~$\phi_1$ is actually the marked~$\node{P}$-node. We make a case distinction over the type of the node~$\phi$.

  \textbf{Case 1:}~$\phi$ is an~$\node{S}$-node.
  From \cref{thm:2-legged-f0-always-upwards} we know that an st-outwards valid ortho-radial representation for~$\phi_1$ exists. As an orthogonal representation with spirality~$0$ exists for the other child node, the combination of these two representations still results in an st-outwards valid ortho-radial representation. \cref{fig:2-leg-fc-after} shows this in an abstract view.

  \textbf{Case 2:}~$\phi$ is a~$\node{P}$-node. From \cref{thm:2-legged-f0-always-upwards} we know that~$\phi_1$ admits an st-outwards valid ortho-radial representation. We also know that an orthogonal representation~$\ogr_2$ of~$\phi_2$ exists with~$\sigma(\ogr_2)=0$. By using a rotation combination of~$[-1,-1,0,0]$ as shown in \cref{fig:2-leg-fc-after}, one can combine both representations into one ortho-radial representation~$\orr$ of~$G$ as the newly created face has rotation~$4$. Every newly created simple essential cycle~$C$ in~$\orr$ has to pass through the outwards directed edges of~$G_1$, one of which has a positive label in~$C$, while the other one has a negative label. Therefore,~$\orr$ is valid. As the legs of~$\phi$ also point radially outwards, the representation is st-outwards.

  The inductive case for~$n > 1$ follows analogously to the base case, only here we use the induction hypothesis instead of \cref{thm:2-legged-f0-always-upwards} to imply an st-outwards valid ortho-radial representation of the child~$\phi_1$.
\end{proof}

Combining the individual results about constructing a valid ortho-radial representation for 2-legged SP-graphs yields the following result.

\begin{theorem}\label{thm:2-legged-linear-time}
  Given a 2-legged series-parallel plane 3-graph~$(G,\emb)$, a fixed outer face~$f_o$, and a fixed inner face~$f_c$, a valid ortho-radial representation of~$G$, if one exists, can be found in~$\bigO{n}$ time.
\end{theorem}
\begin{proof}
  The creation of a decomposition tree of~$G$ is possible in linear time and let~$\phi$ be the node where~$f_c$ is formed. Applying, based on the type of node, either \cref{lem:2-leg-series-value} or \cref{lem:2-leg-parallel-value} at each sub-node of~$\phi$ results in either a \structure{} for every sub-node or in one parallel-node not fulfilling the condition in \cref{lem:2-leg-parallel-value}. If this condition is not fulfilled, it is immediately clear that no ortho-radial representation for the graph~$G$ can exist. Conversely, if every parallel node fulfills the condition, \cref{thm:2-legged-f0-always-upwards} states the requirements for a valid ortho-radial representation of~$\phi$. If these are also met, then there exists a valid ortho-radial representation for~$\phi$ and \cref{cor:2-leg-series-after-fc} implies that then also a valid ortho-radial representation for~$G$ exists. As the size of the decomposition tree is linear to the size of~$G$ and each node only takes constant time to compute the \structure{} and check the conditions, the tree can be traversed in linear time.

  The valid ortho-radial representation can then be computed via a second top-down recursion over the decomposition tree, where each aforementioned result states how an orthogonal or valid ortho-radial representation with the required properties can be constructed and, in turn, what properties the representations of their child-nodes require to do so.
\end{proof}

\subsection{Finding Bend-Minimum Ortho-Radial Representations}\label{sec:2-leg-bend-min}

\cref{thm:2-legged-linear-time} states that a valid ortho-radial representation for a given 2-legged SP-graph~$G$ can be computed in linear time, provided one exists. In the case that no valid ortho-radial representation exists, we now find the minimum number of bends that have to be added to~$G$ to allow a valid ortho-radial representation. Bends are added by adding special \emph{bend-vertices} to edges in~$G$. These allow an edge to artificially bend, while the results of the previous section can still be used. \cref{fig:2-leg-bendmin-example} shows an example of a graph that only admits a valid ortho-radial representation if a bend-vertex is added. The modified decomposition tree includes the bend-vertex via a new~$\node{S}$-node.

\begin{lemma}\label{lem:2-leg-bendmin-bend-vertex-in-tree}
  Let~$(G,\emb)$ be a 2-legged series-parallel plane 3-graph, let~$\mathcal{T}$ be a decomposition tree of~$G$, and let~$H$ be a graph obtained by adding a single bend-vertex at an arbitrary edge~$e$ in~$G$. Then there exists a decomposition tree~$\mathcal{T_H}$ of~$H$ obtained by adding a series-connection with a new~$\node{D}$-node at a specific point in the decomposition tree~$\mathcal{T}$.
\end{lemma}
\begin{proof}
  Let~$\phi$ be the node furthest down in~$\mathcal{T}$ that still contains the edge~$e$ in its induced subgraph~$G_\phi$. Then~$e$ must be a leg of~$G_\phi$. The additional bend vertex in~$H$ can be represented by a series-composition of~$\phi$ with a new~$\node{D}$-node. The order of this series composition depends on whether~$e$ is incident to the starting or end terminal. Let~$\psi$ be a~$\node{S}$-node representing this series-composition. By replacing~$\phi$ with~$\psi$ the resulting tree is a decomposition tree of~$H$.
\end{proof}

\begin{figure}
  \centering\includegraphics{figures/bendmin-example.pdf}
  \caption{On the left, a 2-legged SP-graph without a valid ortho-radial representation, as the left-most face is a triangle, and the decomposition tree of the graph. Adding the blue bend-vertex to the red edge makes the graph admit the valid representation shown on the right. The second decomposition tree includes an~$\node{S}$-node and a~$\node{D}$-node representing the bend-vertex.}\label{fig:2-leg-bendmin-example}
\end{figure}

There are two places in the construction where extra bend-vertices may be required. First in \cref{lem:2-leg-parallel-value}, where the condition for a~$\node{P}$-node forming an orthogonal representation may not be met (see \cref{fig:2-leg-bendmin-example}), and second in \cref{thm:2-legged-f0-always-upwards}, where the central face is formed and a condition ensures that created essential cycles are valid.

Regarding \cref{thm:2-legged-f0-always-upwards}, \cref{fig:2-leg-bendmin-example-fc} shows an example of a graph not fulfilling the condition of the lemma and how the addition of a bend-vertex makes the graph admit a valid ortho-radial representation. The following lemma states that in this case a single bend-vertex is always enough so that the node admits a valid ortho-radial representation. 

\begin{figure}
  \centering\includegraphics{figures/bendmin-example-fc.pdf}
  \caption{On the left, a 2-legged SP-graph where the conditions in \cref{thm:2-legged-f0-always-upwards} are not fulfilled. When adding the blue bend-vertex to the red edge, the graph admits the valid ortho-radial representation shown on the right.}\label{fig:2-leg-bendmin-example-fc}
\end{figure}

\begin{lemma}\label{lem:2-leg-bendmin-para-fc}
  Let~$\phi$ be a~$\node{P}$-node at which the face~$f_c$ should be created and where its children~$\phi_1$ and~$\phi_2$ both are rectilinear-plane. If all the conditions in \cref{thm:2-legged-f0-always-upwards} do not hold and therefore no valid ortho-radial representation exists, the addition of a single bend-vertex is enough so that~$\phi$ admits a valid ortho-radial representation.
\end{lemma}
\begin{proof}
  Let~$G_1$ and~$G_2$ be the induced subgraphs of~$\phi_1$ and $\phi_2$, respectively. Due to the conditions in \cref{thm:2-legged-f0-always-upwards} not being met, we know that one subgraph has the step values~$\mstructureSteps{a}=[0,0,1]$ and the other subgraph has the values~$\mstructureSteps{b}=[x,y,0],\ x,y\in \mn$. Without loss of generality, let~$a=1$ and~$b=2$. As~$\phi$ admits no valid ortho-radial representation, we also know with \cref{eq:2-legged-f0-always-upwards__bend_limitations^z} that~$b_1^l=0$. The addition of a bend-vertex at one of the legs of~$\phi_1$ increases~$b_1^l$ to~$1$. This is enough to fulfill the condition~$b_1^l \geq 0 \land s_2^r>0$ in \cref{eq:2-legged-f0-always-upwards__bend_limitations^z} and the existence of a valid ortho-radial representation follows.
\end{proof}

Regarding \cref{lem:2-leg-parallel-value}, assume we encounter a~$\node{P}$-node~$\phi$ not containing~$f_c$ for which the condition
$b_1^r + b_2^l \geq 2$
does not hold. Then the addition of~$2-b_1^r - b_2^l$ bend vertices along some edges would be the minimum required amount such that an orthogonal representation for~$\phi$ exists. But one has to decide where to put these bend vertices. In general, meaning series-parallel 4-graphs, this is not trivial to decide~\cite{DIDIMO22}. As both children are 2-legged though, there always exist the legs of each child, which can be selected for bending. The problem however is that the distribution of bend-vertices could influence the step values of~$\phi$, which at a later recursion step may be important. For example, the optimal left step value may only be achievable if the bend-vertex is added at one specific edge, possibly somewhere inside the graph. In general, these placements also differ per value and one would have to move the bend-vertices to the optimal place according to the desired properties of the representation. \cref{fig:2-leg-bendmin-example-different-step} shows a situation where a zero step value of~$1$ is only achievable when placing the bend-vertex on the edge~$v$ while a left step value of~$1$ is only achievable when placing the bend-vertex on the edge~$u$. We now show that one does not have to check every edge in the graph when adding bend-vertices. Rather, it is enough to only consider the four legs of the children of~$\phi$.

\begin{figure}
  \centering\includegraphics{figures/bendmin-p-node-different-step.pdf}
  \caption{On the left, a 2-legged SP-graph where the condition in \cref{lem:2-leg-parallel-value} is not fulfilled and a bend-vertex must be added. On the right, two orthogonal representations with a bend-vertex on the edges~$v$ or~$u$. The zero and left step values depends on where the bend-vertex is placed.}\label{fig:2-leg-bendmin-example-different-step}
\end{figure}

First up, we show that placing bend-vertices on the legs of a graph results in the highest possible bend and step values. Afterwards, we use this knowledge to calculate the~$\structure{}$ of a~$\node{P}$-node including bend-vertices.

\begin{lemma}\label{lem:2-leg-bendmin-leg-enough}
  Let~$(G,\emb)$ be a \twlegrecplsptg{} and let~$H$ be the graph obtained by adding a single bend-vertex at an arbitrary edge~$e$ in~$G$. Then there exists a graph~$F$ which is obtained by instead adding the bend-vertex at a leg of~$G$ so that the bend values as well as the left and right step values of~$H$ are smaller or equal to those of~$F$.
\end{lemma}
\begin{proof}

  Let~$\mathcal{T}$ be the decomposition tree of~$G$ and let~$\mathcal{T_H}$ be the decomposition tree of~$H$ from \cref{lem:2-leg-bendmin-bend-vertex-in-tree}. The newly added~$\node{D}$-node has the \structure{}~$\mstructure{} = [1,1,0,0,1]$ where its bend values are both~$1$ and the left and right step values are both~$0$. The linearity of the equations in \cref{lem:2-leg-series-value} and \cref{lem:2-leg-parallel-value} imply that the bend and step values of the root of~$\mathcal{T_H}$, and therefore of~$H$, are at most by~$1$ greater than the ones of~$G$.

  What is left to show is that the addition of a bend-vertex at one of the legs of~$G$ increases these values by at least~$1$. We again represent this bend-vertex by a series-composition of~$G$ with a~$\node{D}$-node. No matter on which leg the bend-vertex is placed, we know due to \cref{lem:2-leg-series-value} that the bend values of this new graph always increase by~$1$. To get the same result for the left and right step values, one has to pick a specific leg for bending. Let~$s^l_G, b^r_G$, and~$b^l_G$ be the left step as well as the bend values of~$G$. We distinguish between two cases.

  \textbf{Case 1:}~$b^l_G> 0$. Then Equation~(\ref{eq:-2leg-series-value-sl3}) in \cref{lem:2-leg-series-value} implies that the addition of a bend vertex at the leg~$e^t$ results in a graph~$F$ with left step value~$s^l_F  \geq s^l_G + 1$.

  \textbf{Case 2:}~$b^r_G \geq 0$. We can assume that~$b^l_G=0$ and due to \cref{lem:2-leg-b0-implies-s0},~$s^l_G=0$ follows. Then Equation~(\ref{eq:-2leg-series-value-sl2}) in \cref{lem:2-leg-series-value} implies that the addition of a bend vertex at the leg~$e^s$ results in a graph~$F$ with left step value~$s^l_F \geq b^r_G \geq s^l_G + 1$.

  Proving the same fact for the right step value of~$F$ works analogous.
\end{proof}

\begin{lemma}\label{lem:2-leg-bendmin-parallel}
  Let~$\phi$ be an inner~$\node{P}$-node not containing~$f_c$ for which
\[b_1^r + b_2^l < 2.\] 
Then~$2-b_1^r - b_2^l$ bend-vertices have to be added to realize an orthogonal representation for~$\phi$. To calculate the \structure{} for~$\phi$ including these bend-vertices, it is enough to look at all distributions of the bend-vertices on~$e^s_1,e^t_1,e^s_2,e^t_2$ and take per bend and step value the highest one over all distributions.
\end{lemma}
\begin{proof}
According to \cref{lem:2-leg-bendmin-leg-enough}, the addition of a bend-vertex on one of the leg of a child-graph always increases its bend values by one. Then~$2-b_1^r-b_2^l$ bend-vertices are enough to fulfill the condition~$b_1^r+b_2^l \geq 2$.

Regarding the calculation of the \structure{} of~$\phi$, \cref{lem:2-leg-bendmin-leg-enough} shows that for the child nodes all values in the structure except~$s^z$ assume their highest value if the bend-vertices are placed at their legs. Therefore, only the distribution of bend-vertices to~$e^s_1,e^t_1,e^s_2,e^t_2$ have to be considered. Note that the exclusion of~$s^z$ in \cref{lem:2-leg-bendmin-leg-enough} is not a problem as even if a bend-vertex would increase the zero step value of a child, then only an orthogonal representation of the child with spirality~$0$ would benefit from this increase. But these bend-vertices are explicitly added to increase the spirality of the child nodes representation so that an orthogonal representation of the parallel composition exists in the first place. Therefore, an orthogonal representation of the child with spirality~$0$ can never be used in the construction.
\end{proof}

We know that the number of edges to add is at most two, and so there are at most~$16$ different distributions to check. Per distribution, the step values can be computed via \cref{lem:2-leg-series-value} by combining each child serially with a~$\node{D}$-node per bend-vertex. In total, we form the following result.

\begin{theorem}
  Given a 2-legged series-parallel plane 3-graph~$(G,\emb)$, a fixed outer face~$f_o$, and a fixed inner face~$f_c$, a bend-minimum valid ortho-radial representation of~$G$ if one exists, can be found in~$\bigO{n}$ time.
\end{theorem}
\begin{proof}
  The same approach as described in \cref{thm:2-legged-linear-time} can be used. The difference is that if a node in the recursion does not fulfill the conditions, one has to add bend-vertices as described in \cref{lem:2-leg-bendmin-parallel} and \cref{lem:2-leg-bendmin-para-fc}. In both situations, the addition of bend-vertices and the calculation of the \structure{} of these nodes only take constant time.

  What is left to prove is that the resulting ortho-radial representation is actually bend-minimum. For this, we define for a given node~$\phi$ in the decomposition tree~$\mathcal{B}(\phi)$ to be the number of bend-vertices added by \cref{lem:2-leg-bendmin-para-fc,lem:2-leg-bendmin-parallel} in the recursion up to~$\phi$. Moreover, for an arbitrary valid ortho-radial representation~$\orr$ with bend-vertices we define~$b(\orr)$ to be the number of bend-vertices specifically added in~$\orr$. Let~$\phi$ be a node in the decomposition tree of $G$. 
  We now prove by induction over the depth of the subtree~$n$ rooted at~$\phi$ that~$\mathcal{B}(\phi)=b(\orr_\phi^{\min})$, where~$\orr_\phi^{\min}$ is a bend-minimum valid ortho-radial representation of the induced subgraph of~$\phi$. This implies that once the recursion has reached the root~$\tau$, the budget~$\mathcal{B}(\tau)$ equals the minimum number of bends required for a valid ortho-radial representation of the whole graph~$G$.
  
  \textbf{Base case:} If~$n=1$, then~$\phi$ is a leaf node and~$\mathcal{B}(\phi)=0=b(\orr_\phi^{\min})$, so the statement is trivial.
  
  \textbf{Inductive case:} Let~$n > 1$ and assume that the statement holds for all~$k<n$. Then~$\phi$ is a node of~$\mathcal{T}$ that is not a leaf and denote by~$\phi_1$ and~$\phi_2$ the children of~$\phi$. The subtrees of the two children have depth at most~$n-1$, so the induction hypothesis implies that both~$\mathcal{B}(\phi_1)=b(\orr_{\phi_1}^{\min})$ and~$\mathcal{B}(\phi_2)=b(\orr_{\phi_2}^{\min})$. We also know that~$\mathcal{B}(\phi)=\mathcal{B}(\phi_1)+\mathcal{B}(\phi_2)+b_\phi$ where~$b_\phi$ are the number of bends in the construction that are used at the node~$\phi$ to realize a valid ortho-radial representation. Let~$\orr_\phi^{\min}$ be a bend-minimum valid ortho-radial representation of~$\phi$ and let~$\orr_1$ as well as~$\orr_2$ be the induced valid ortho-radial representation of~$\phi_1$ and~$\phi_2$.
  
  From the inductive hypothesis we know that~$b(\orr_1) \geq \mathcal{B}(\phi_1)$ and~$b(\orr_2) \geq \mathcal{B}(\phi_2)$. In actuality, as~$\orr_1$ and~$\orr_2$ are the induced representations of the whole representation~$\orr$, they may have more bend-vertices than would be necessary for each subgraph on its own. So let~$0 \leq m_1 = b(\orr_1)-\mathcal{B}(\phi_1)$ and~$0 \leq m_2 = b(\orr_2)-\mathcal{B}(\phi_2)$. We now show~$b_\phi \leq m_1 + m_2$ since this then implies that
  \[\mathcal{B}(\phi)=\mathcal{B}(\phi_1)+\mathcal{B}(\phi_2)+b_\phi \leq b(\orr_1) + b(\orr_2) = b(\orr_\phi^{\min}).\]
  If, according to the construction, no bend-vertices have to be added at~$\phi$, we have~$b_\phi=0$ and the inequality trivially holds. In the case where~$b_\phi > 0$, \cref{lem:2-leg-bendmin-para-fc} and \cref{lem:2-leg-bendmin-parallel} show that if fewer than~$b_\phi$ bend-vertices are added to the already existing bend-vertices in~$\phi_1$ and~$\phi_2$, no valid ortho-radial representation of~$\phi$ exists. This would be a contradiction to the existence of~$\orr_\phi^{\min}$. This proves~$\mathcal{B}(\phi) \leq b(\orr_\phi^{\min})$, and as~$\mathcal{B}(\phi) \geq b(\orr_\phi^{\min})$ holds by definition, equality follows.
\end{proof}