generalStep.tex

\subsection{General Step Values}\label{sec:general-step-values}
\cref{sec:sp3graph2-leg} introduces the notion of step values, which are used to ensure the existence of edges with desired labels. For this, the left and right step value~$s^l$ and~$s^r$ measures how much a representation of the graph can bend in one direction, while having at least one edge per st-path that is bent into the opposite direction. The zero step value~$s^z$ indicates if an orthogonal representation exists with an st-path that only has relative label~$0$. We now generalize the left and right step values into a combined step value~$s$, and also add a new step value~$s^{lr}$.

The step values~$s^l$ and~$s^r$ only ensure that an edge~$e$ in every st-path exists with relative label~$\lrefs{e}<0$ or~$\lrefs{e}>0$, but gives no indication of what the actual relative label of~$e$ may be. The new step value includes a parameter indicating the required relative label for~$e$.

\begin{figure}
    \centering\includegraphics{figures/g2leg-value-example.pdf}
    \caption{A 2-legged SP-graph and examples of orthogonal representations implying the step value expressions below each representation.}\label{fig:g2leg-values-example}
\end{figure}
\begin{definition}\label{def:g2leg-bend-step-value}
    Let~$(G,\emb)$ be a \twlegrecplsptg{}. We define the \emph{bend step value}~$s:\mz \rightarrow 2^\mz$ as a function for which the following holds.
    \[x \in s(y) \iff \exists\ \ogr \in \Omega(G,\emb): \sigma(\ogr)=x,\ \forall\ P \in \stpaths: \exists\ e \in P: \lrefs{e} = y\]
    The expression~$x \in s(y)$ is called a \emph{step value expression}.
\end{definition}

If~$x \in s(y)$ for some~$x,y\in \mz$ then there exists an orthogonal representation, where every st-path first contains an edge with relative label~$y$ before resulting in a total spirality of~$x$. See \cref{fig:g2leg-values-example} for some examples of step value expressions and matching representations. The following lemma shows how some step value expressions imply others. For better clarity, we use the definition of signed intervals~$\signedInterval{x}{y}$.

\begin{lemma}\label{lem:g2leg-step-implications}
    Let~$(G,\emb)$ be a \twlegrecplsptg{} with bend step value~$s$. Then the following statements hold.
    \begin{align}
         x \in s(y) &\implies x \in s(y') &\forall\ y' \in \signedInterval{0}{y}\label{eq:g2leg-step-implications-1}\\
         x \in s(y) &\implies x \in s(y') &\forall\ y' \in \signedInterval{0}{x}\label{eq:g2leg-step-implications-4}\\
         x \in s(y) &\implies x' \in s(y)&\forall\ x' \in \signedInterval{x}{y}\label{eq:g2leg-step-implications-2}\\
         x \in s(y) &\implies x-z \in s(y-z)&\forall\ z \in \signedInterval{0}{y}\label{eq:g2leg-step-implications-3}
    \end{align}
\end{lemma}

\begin{proof}
    For \cref{eq:g2leg-step-implications-1}, the step value expression~$x \in s(y)$ implies the existence of an orthogonal representation~$\ogr$ with~$\lrefs{e}=y$ for some edge in every st-path. Along such an st-path there must exist edges between~$e^s$ and~$e$ having any relative label between~$0$ and~$y$. This directly implies~$x \in s(y')$ for~$y' \in \signedInterval{0}{y}$.

    Regarding \cref{eq:g2leg-step-implications-4}, the step value expression~$x \in s(y)$ implies an orthogonal representation~$\ogr$ with~$\lrefs{e^t}=\sigma(\ogr)=x$. Along every st-path there must exist edges with all values between~$0$ and~$x$. This directly implies~$x \in s(y')$ for~$y' \in \signedInterval{0}{x}$.

    For \cref{eq:g2leg-step-implications-2}, let, without loss of generality,~$x<y$. We show this fact for~$x'=x+1$ and the statement follows from iteration. Because~$x \in s(y)$ holds, there exists an orthogonal representation~$\ogr$ of~$G$ with~$\sigma(\ogr)=x$ such that every st-path contains an edge~$e$ with~$\lrefs{e}=y>x$. So there must exist vertices~$u,v,w$ along every st-path between every such edge~$e$ and~$e^t$ with~$\rot(uv,vw)=-1$. See \cref{fig:g2leg-bend-step-implications-a} for an example. \cref{lem:2-leg-elementarytransform} then implies the existence of another orthogonal representation~$\ogr'$ with~$\sigma(\ogr')=\sigma(\ogr)+1=x+1=x'$. Moreover,~$\ogr'$ and~$\ogr$ only differ in its rotation at each vertex~$v$ and for every edge~$e$ it still holds that~$\lrefs{e}=y$. The existence of~$\ogr'$ then implies~$z \in s(y)$.

    \begin{figure}
        \centering\includegraphics{figures/g2leg-bend-step-implications.pdf}
        {
            \phantomsubcaption\label{fig:g2leg-bend-step-implications-a}
            \phantomsubcaption\label{fig:g2leg-bend-step-implications-b}
        }
        \caption{A graph with two pairs of orthogonal representations. The existence of the left representation in each pair implies the existence of the right. The blue vertex~$v$ changes its rotation in the path between the representations.}\label{fig:g2leg-bend-step-implications}
    \end{figure}
    
    For \cref{eq:g2leg-step-implications-3}, let, without loss of generality,~$y<0$. We show this fact for~$z=-1$ and the statement follows from iteration. Because~$x \in s(y)$ holds, there exists an orthogonal representation~$\ogr$ of~$G$ with~$\sigma(\ogr)=x$ such that every st-path contains an edge~$e$ with~$\lrefs{e}=y<0$. So there must exist vertices~$u,v,w$ along every st-path between~$e^s$ and~$e$ with~$\rot(uv,vw)=-1$. See \cref{fig:g2leg-bend-step-implications-b} for an example. \cref{lem:2-leg-elementarytransform} then implies the existence of another orthogonal representation~$\ogr'$ with~$\sigma(\ogr')=\sigma(\ogr)+1=x+1=x-z$. Moreover,~$\ogr'$ and~$\ogr$ only differ in its rotation at each vertex~$v$, and for every edge~$e$ it holds that~$\lrefs{e}=\lrefs{e}+1=y+1=y-z$. The existence of~$\ogr'$ then implies~$x-z \in s(y-z)$.
\end{proof}


\cref{lem:g2leg-step-implications} directly implies that~$s(y)$ is an interval for every~$y\in \mz$ as well as~$x \leq s^l\ \forall\ x \in s(-1)$ and~$x \geq -s^r\ \forall\ x \in s(1)$. It also holds that~$s(0)=[-b^l,b^r]$. The bend step value therefore also represents the old bend values~$b^l,b^r$. We will from now on use~$x \in s(0)$ instead of~$x\leq b^r,b^l$.

The old step values~$s^l$ and~$s^r$ as well as the new bend step value~$s$ only imply the existence of one edge with a given relative label. The condition for a valid ortho-radial representation requires an edge with a positive and with a negative relative label, though. Oftentimes, the spirality~$x$ implied by the step value expression~$x \in s(y)$ is enough to also imply an edge of the opposite sign, but if~$x=0$, this may not always work. We therefore introduce a new step value which indicates that both a positive and a negative relative label is present, while the representation has spirality~$0$.


\begin{definition}
    Let~$(G,\emb)$ be a \twlegrecplsptg{}. We define the \emph{left-right step value}~$\slr$ as
    \[\slr = \begin{cases}
        1 \caseif \exists\ \ogr \in \Omega(G,\emb): \sigma(\ogr)=0, \forall P \in \stpaths: \exists\ e,e' \in P: \lrefs{e}<0,\ \lrefs{e'}>0 \\
        0 \caseotherwise .
    \end{cases}\]
\end{definition}

The following lemma shows how a left-right step value~$\slr=1$ implies other step value expressions.
\begin{lemma}\label{lem:g2leg-slr-implications}
    Let~$(G,\emb)$ be a \twlegrecplsptg{} with~$\slr=1$. Then~$0 \in s(1)$,~$0 \in s(-1)$, as well as~$2,-2 \in s(0)$ follows.
\end{lemma}
\begin{proof}
    If~$\slr=1$, then there exists an orthogonal representation~$\ogr$ of~$G$ with~$\sigma(\ogr)=0$ and edges with a positive as well as a negative relative label in every st-path. These edges have at least relative label~$1$ and~$-1$, respectively.~$0 \in s(-1)$ and~$0 \in s(1)$ then follows directly from \cref{def:g2leg-bend-step-value}.~$2,-2 \in s(0)$ follows from \cref{lem:2-leg-bgeq2IfBothPosAndNeg}.
\end{proof}


Having both new step values defined, we now adapt the \structure{} of an orthogonal representation to be simply~$[s,s^z,\slr]$ instead of~$[b^l,b^r,s^l,s^r,s^z]$ . Each~$\node{Q}$-node has the \structure{}~$[s_\node{Q},1,0]$ with~$s_\node{Q}(0)=\{0\}$ and each~$\node{D}$-node has the \structure{}~$[s_\node{D},1,0]$ with~$s_\node{D}(0)=\{0,1\}$. We now show analogous to \cref{sec:sp3graph2-leg} how the bend step value and left-right step value of inner nodes are dependent on the ones of their child nodes. To more easily describe this correlation, we use the~$+$ operator between sets to mean~$A+B \defeq \{a+b\ |\ a \in A, b \in B\}$.

\begin{lemma}\label{lem:g2leg-S-values}
    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~$\mstructuren{1}$ be the \structure{} of~$\phi_1$ and~$\mstructuren{2}$ be the \structure{} of~$\phi_2$. Then the bend step value~$s$ and the left-right step value~$\slr$ of~$\phi$ satisfy the following.
    \begin{align}
        s(y) &= \Bigl(\bigcup_{i\in \signedIntervalO{0}{y}} (\st{1}{0}\cap\{i\}) + \st{2}{y-i}\Bigr) \cup \st{1}{y} + \st{2}{0} \label{eq:g2leg-S-values-s}\\
              \slr =1 &\iff \bigvee \begin{cases}
                \slr_1=1, \slr_2=1, \\
                0 \in \st{1}{-i} \land 0 \in \st{2}{i} \text{ for } i \in \{-1,1\},\\
                i \in \st{1}{0} \land -i \in \st{2}{-2i} \text{ for } i \in \{-1,1\}, \\
                i \in \st{1}{-i} \land -i \in \st{2}{0} \text{ for } i \in \{-1,1\}
              \end{cases}\label{eq:g2leg-S-values-slr}
    \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$,~$s_2,t_2$ be the terminals of~$G_2$, and~$e^s_1,e^s_2,e^t_1,e^t_2$ be the legs of~$G_1$ and~$G_2$.

    \begin{figure}
        \centering\includegraphics{figures/g2leg-S-values-step.pdf}
        {
            \phantomsubcaption\label{fig:g2leg-S-step-example-a}
            \phantomsubcaption\label{fig:g2leg-S-step-example-b}
        }
        \caption{Two series-compositions resulting in the step value expression~$2 \in s(-2)$, but with different properties of the subgraphs~$G_1$ and~$G_2$.}
    \end{figure}

    We start with \cref{eq:g2leg-S-values-s} and first show the ''$\supseteq$''-direction. Let~$y \in \mz$ and first let~$i \in \signedIntervalO{0}{y}$ such that~$z \in (\st{1}{0}\cap\{i\}) + \st{2}{y-i}$. For~$\st{1}{0} \cap \{i\}$ to not be the empty set,~$i \in \st{1}{0}$ must hold and for~$z$ to be in the whole set it follows that~$z-i\in \st{2}{y-i}$. Then there exists an orthogonal representation~$\ogr_1$ of~$G_1$ with~$\sigma(\ogr_1)=i$ and an orthogonal representation~$\ogr_2$ of~$G_2$ with~$\sigma(\ogr_1)=z-i$ where in every st-path an edge~$e$ exists with~$\lref{s_2}{e}=y-i$. Let~$\ogr$ be the orthogonal representation of~$G$ obtained by combining~$\ogr_1$ and~$\ogr_2$.~\cref{fig:g2leg-S-step-example-a} shows this for~$i=-1$ and~$3 \in\st{2}{-1}$ resulting in the step value expression~$2 \in s(-2)$. Then every edge~$e$ from above now has relative label~$\lrefs{e}=\sigma(\ogr_1)+\lref{s_2}{e}=i+y-i=y$ and~$\ogr$ has spirality~$\sigma(\ogr)=i+z-i=z$. This implies~$z \in s(y)$. Second, assume~$z \in \st{1}{y} + \st{2}{0}$. Then there exists an orthogonal representation~$\ogr_1$ of~$G_1$ with~$\sigma(\ogr_1)=x$ and an edge~$e$ in every st-path with~$\lref{s_1}{e}=y$, as well as an orthogonal representation~$\ogr_2$ of~$G_2$ with~$\sigma(\ogr_2)=z-x$. The combined representation has spirality~$z$, and the relative labels of edges~$e$ from above stay the same. This also implies~$z \in s(y)$. This situation is depicted in \cref{fig:g2leg-S-step-example-b}, where~$-1 \in \st{1}{-2}$ and~$3 \in \st{2}{0}$ results in~$2 \in s(-2)$.

    Now to the ''$\subseteq$''-direction of \cref{eq:g2leg-S-values-s}. Without loss of generality, let~$y\leq 0$ and let~$z \in s(y)$. Then there exists an orthogonal representation~$\ogr$ of~$G$ with~$\sigma(\ogr)=z$ and an edge~$e$ in every st-path with~$\lrefs{e}=y$. Let~$\ogr_1$ and~$\ogr_2$ be the induced orthogonal representations of~$G_1$ and~$G_2$, and let~$i \defeq \sigma(\ogr_1)$ and therefore~$\sigma(\ogr_2)=z-i$. There are two possible cases.
    
    \textbf{Case 1:} Every st-path in~$G_1$ already contains an edge with~$y = \lrefs{e}= \lref{s_1}{e}$. This implies~$i \in \st{1}{y}$. The existence of~$\ogr_2$ also implies~$z-i \in \st{2}{0}$ and therefore~$z \in \st{1}{y} + \st{2}{0}$ follows.

    \textbf{Case 2:} There exists an st-path~$P_1$ in~$G_1$, such that~$y < \lrefs{e}= \lref{s_1}{e}$ for all~$e \in P_1$. This also implies~$i \in \signedIntervalO{0}{y}$. Now assume that~$z-i \notin \st{2}{y-i}$ would hold. Then there exists a path~$P_2$ through~$G_2$ such that~$y-i <\lref{s_2}{e}$ for all~$e \in P_2$. The path~$P=P_1+P_2$ then is an st-path of~$G$, and it holds for all~$e \in P$ that
    \[\lrefs{e} = \begin{cases}
        \lref{s_1}{e}>y \caseif e \in G_1, \\
        \sigma(\ogr_1) + \lref{s_2}{e} > i+y-i = y \caseotherwise.
    \end{cases}\]
    This is a contradiction to~$z \in s(y)$. So~$z-i \in \st{2}{y-i}$ must hold. As~$\sigma(\ogr_1)=i$, it follows that~$z \in (\st{1}{0} \cap \{i\}) + \st{2}{y-i}$.

    \begin{figure}
        \centering\includegraphics{figures/g2leg-S-values.pdf}
        {
            \phantomsubcaption\label{fig:g2leg-S-slr-example-a}
            \phantomsubcaption\label{fig:g2leg-S-slr-example-b}
            \phantomsubcaption\label{fig:g2leg-S-slr-example-c}
            \phantomsubcaption\label{fig:g2leg-S-slr-example-d}
        }
        \caption{Ways of creating a left-right step value~$\slr=1$ in a series composition of two subgraphs~$G_1$ and~$G_2$.}\label{fig:g2leg-S-slr-example}
    \end{figure}


    Now to \cref{eq:g2leg-S-values-slr} where we start with the ''$\impliedby$''-direction. If~$\slr_1=1$ or~$\slr_2=1$, it is obvious that also~$\slr=1$ since there always exists an orthogonal representation of the other subgraph with spirality~$0$ as for example in \cref{fig:g2leg-S-slr-example-a}. Without loss of generality, let~$i=1$ and let~$\ogr_1$ and~$\ogr_2$ be such that one of the other conditions hold, and let~$\ogr$ be the combined orthogonal representation of~$G$.

    If~$0 \in \st{1}{i}$ and~$0 \in \st{2}{-i}$, then there exist edges~$e$ in every st-path of~$G_1$ with~$\lrefs{e}=\lref{s_1}{e}=i$ and there exist edges~$e'$ in every st-path of~$G_2$ with~$\lrefs{e'}=\sigma(\ogr_1) + \lref{s_2}{e'}=-i$. So in~$\ogr$ every st-path has a positive relative label in~$G_1$ and a negative relative label in~$G_2$ as seen in \cref{fig:g2leg-S-slr-example-b}. Finally,~$\sigma(\ogr)=0+0=0$ implies~$\slr=1$.
    
    If~$i \in \st{1}{0}$, then~$\lrefs{e^t}=\sigma(\ogr_1)=i$ and with~$-i \in \st{2}{-2i}$ there exists an edge in every st-path of~$G_2$ with~$\lrefs{e}=\sigma(\ogr_1)+\lref{s_2}{e}=i-2i=-1$. See \cref{fig:g2leg-S-slr-example-c} for an example. Due to~$\sigma(\ogr)=i-i=0$,~$\slr=1$ follows.
    
    Finally, if~$i \in \st{1}{-i}$ holds (see \cref{fig:g2leg-S-slr-example-d}), then~$\lrefs{e^t}=\sigma(\ogr_1)=1$ and there exists an edge~$e$ every st-path of~$G_1$ with~$\lrefs{e}=\lref{s_1}{e}=-1$. With~$-i \in \st{2}{0}$, also~$\sigma(\ogr)=i-i=0$ holds and~$\slr=1$ follows.

    For the ''$\implies$''-direction, assume~$\slr=1$. Then there exists an orthogonal representation of~$G$ having spirality~$0$ with a positive and a negative relative label in every path. When looking at which of these labels are contained in which subgraph, the situation never arises where two st-paths~$P$ and~$P'$ exist, such that~$P$ only has negative relative labels in~$G_1$ and~$P'$ only has negative relative labels in~$G_2$. Because then there exists a third st-path created by the parts of~$P$ and~$P'$ not containing a negative relative label, which now in total would not contain a negative relative label as well. This is a contradiction to~$\slr=1$ and the same argumentation holds for positive instead of negative relative labels. Due to this, at least~$G_1$ or~$G_2$ must have a positive or negative relative label in every of its st-paths and depending on which subgraph contains which relative label, we deduce one of the four conditions. We now make a case distinction.

    \textbf{Case 1:}~$\sigma(\ogr_1)=0$. Then~$\sigma(\ogr_2)=0$ so that~$\ogr$ has the spirality~$0$. If now~$G_1$ also contains both a positive and negative relative label in every st-path,~$\slr_1=1$ follows, while if~$G_2$ contains both a positive and a negative relative label in every st-path,~$\slr_2=1$.

    If~$G_1$ contains relative labels of one sign in every st-path but not of the other, then~$0 \in \st{1}{i}$ holds with~$i \in \{1,-1\}$, depending on which sign is present. To still have~$\slr=1$,~$G_2$ must contain relative labels of the opposite sign in every st-path, which implies~$0 \in \st{2}{-i}$.
    
    \textbf{Case 2:}~$\sigma(\ogr_1)=x<0$. Then~$\sigma(\ogr_2)=-x$ for~$\ogr$ to have spirality~$0$. If now~$G_1$ also contains a positive relative label in every st-path, then~$x \in \st{1}{1}$, which with \cref{lem:g2leg-step-implications} also implies~$-1 \in \st{1}{1}$. Due to~$\sigma(\ogr_2)=-x$, we also know from \cref{lem:g2leg-step-implications} that at least~$1 \in \st{2}{0}$. With~$i=-1$ we now have~$i \in \st{1}{-i}$ and~$-i \in \st{2}{0}$.

    If~$G_2$ contains a positive relative label in every st-path then for every edge~$e$ in~$G_2$ with~$\lrefs{e}=1$ we know~$\lref{s_2}{e}=-\sigma(\ogr_1)+\lrefs{e}=-x+1$. This implies~$-x \in \st{2}{-x+1}$ and~$1 \in \st{2}{2}$ follows from \cref{eq:g2leg-step-implications-3} with~$z=-x-1$. Due to~$\sigma(\ogr_1)=x$, we also know from \cref{lem:g2leg-step-implications} that at least~$-1 \in \st{1}{0}$ and with~$i=-1$ we now have~$i \in \st{1}{0}$ and~$-i \in \st{2}{-2i}$.
    
    \textbf{Case 3:}~$\sigma(\ogr_1)>0$, the same argumentation as in Case 2 implies with~$i=1$ that~$i \in \st{1}{-i}$ and~$-i \in \st{2}{0}$, as well as~$i \in \st{1}{0}$ and~$-i \in \st{2}{-2i}$.
\end{proof}

\begin{figure}
    \centering\includegraphics{figures/g2leg-P-values.pdf}
    \caption{On the left, two orthogonal representations of the graphs~$G_1$ and~$G_2$ representing the shown step value expressions. On the right, an orthogonal representation of the parallel-composition of~$G_1$ and~$G_2$ and its implying step value expression using the representations on the left.}\label{fig:g2leg-P-values}
\end{figure}

\begin{lemma}\label{lem:g2leg-P-values}
    Let~$\phi$ be a rectilinear-plane~$\node{P}$-node not containing~$f_c$ with its two children~$\phi_1$ and~$\phi_2$ having \structure{}s~$\mstructuren{1}$ and~$\mstructuren{2}$, respectively. Then the bend step value~$s$ and the left-right step value~$\slr$ of~$\phi$ satisfy the following.
    \[            s(0)= \Bigl[\min\bigl((\st{1}{0}-2) \cap \st{2}{0}\bigr),\max\bigl(\st{1}{0} \cap (\st{2}{0}+2)\bigr)\Bigr]\]
    \begin{numcases}{x \in (y) \iff}
        x \in s(0) & \emph{if} ~$y \in \signedInterval{0}{x}$, \label{eq:g2leg-P-values-sx}\\ 
        x \in (\st{1}{y+1}-1) \cap (\st{2}{y}+1) & \emph{if}~$y \notin \signedInterval{0}{x} \land y < 0$,\label{eq:g2leg-P-values-ys0}\\
        x \in (\st{1}{y}-1) \cap (\st{2}{y-1}+1) & \emph{if}~$y \notin \signedInterval{0}{x} \land y > 0$ \label{eq:g2leg-P-values-yg0}
    \end{numcases}
    \[\slr=1  \iff 2 \in \st{1}{0} \land -2 \in \st{2}{0} \]
\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$.

    We start with the bend step value~$s$ and let~$y\in \mz$. Equality for~$y=0$ is a direct implication of \cref{lem:2-leg-parallel-value} and Term~(\ref{eq:g2leg-P-values-sx}) follows from \cref{eq:g2leg-step-implications-4}. We show both directions for Term~(\ref{eq:g2leg-P-values-ys0}) separately, and we start with the ''$\supseteq$''-direction. So let~$y<0$ and let~$x \in (\st{1}{y+1}-1) \cap (\st{2}{y}+1)$. Then there exists an orthogonal representation~$\ogr_1$ of~$G_1$ with~$\sigma(\ogr_1)=x+1$ and an edge in every st-path with~$\lref{s_1}{e}=y+1$, as well as an orthogonal representation~$\ogr_2$ of~$G_2$ with~$\sigma(\ogr_2)=x-1$ and an edge~$e$ in every st-path with~$\lref{s_2}{e}=y$. \cref{fig:g2leg-P-values} depicts the orthogonal representations of~$G_1$ and~$G_2$ for the case~$2 \in s(-2)$. Using a rotation combination of~$[r_1^s,r_2^s, r_1^t, r_2^t] = [-1,0,0,1]$ results in a combined orthogonal representation~$\ogr$ of~$G$, as the rotation of the newly created face~$f$ between~$G_1$ and~$G_2$ is 
    \[\rot(f)=\infoMath{\rot(e^s_2,e^s_1)}{ = 1} + \sigma(\ogr_1)-\sigma(\ogr_2)+\infoMath{\rot(e^t_1,e^t_2)}{=1}=1+x+1-(x-1)+1=4.\] The spirality of~$\ogr$ is then~$\sigma(\ogr)=r_1^s + \sigma(\ogr_1) + r_1^t = -1 + x+1 + 0= x$.
    Moreover, for every edge~$e$ in~$G_1$ with~$\lref{s_1}{e}=y+1$ it now follows that~$\lrefs{e}=r_1^s+\lref{s_1}{e}=-1+y+1=y$ and for every edge~$e$ in~$G_2$ with~$\lref{s_2}{e}=y$ it follows that~$\lrefs{e}=r_2^s+\lref{s_2}{e}=y$. In total, this implies~$x \in s(y)$.
    The proof of the ''$\supseteq$''-direction for Term~(\ref{eq:g2leg-P-values-yg0}) follows analogously, only here the rotation combination~$[r_1^s,r_2^s,r_1^t,r_2^t] =[0,1,-1,0]$ is used.

    For the ''$\subseteq$''-direction of Term~(\ref{eq:g2leg-P-values-ys0}), let~$x \in s(y)$ and again let~$y<0$. Then there exists an orthogonal representation~$\ogr$ of~$G$ with~$\sigma(\ogr)=x$ and an edge~$e$ in every st-path having~$\lrefs{e}=y$ with~$y \notin \signedInterval{0}{x}$. This implies~$x>y$. As~$\lrefs{e^s}=0$ and~$\lrefs{e^t}=x$, the edges with relative label~$y$ must be present in~$G_1$ and~$G_2$. Relative to~$e^s_1$ and~$e^s_2$ these edges have the labels~$\lref{s_1}{e}=\lrefs{e}-r_1^s=y-r_1^s$ and~$\lref{s_2}{e}=\lrefs{e}-r_2^s=y-r_2^s$. With~$\ogr_1$ and~$\ogr_2$ being the induced orthogonal representations of~$G_1$ and~$G_2$, we know~$x-r_1^s-r_1^t = \sigma(\ogr_1)\in \st{1}{y-r_1^s}$. \cref{eq:g2leg-step-implications-3,eq:g2leg-step-implications-1} with~$r_1^s,r_1^t\in \{-1,0\}$ first imply~$x-r_1^t+1 \in \st{1}{y+1}$ and finally~$x+1 \in \st{1}{y+1}$. Similarly,~$x-r_2^s-r_2^t \in \st{2}{y-r_2^s}$ implies with \cref{eq:g2leg-step-implications-2,eq:g2leg-step-implications-3} as well as~$r_2^s,r_2^t \in \{0,1\}$ that~$x-1 \in \st{2}{y}$. In total,~$x \in (\st{1}{y+1}-1)\cap(\st{2}{y}+1)$ follows. The proof for Term~(\ref{eq:g2leg-P-values-yg0}) follows analogously.

    Now on to the equivalence proof for~$\slr=1$. For the ''$\impliedby$''-direction, let~$\ogr_1$ be an orthogonal representation of~$G_1$ with~$\sigma(\ogr_1)=2$ and let~$\ogr_2$ be an orthogonal representation of~$G_2$ with~$\sigma(\ogr_2)=-2$. Using rotation combination~$r_1^s=r_1^t=-1$ and~$r_2^s=r_2^t=1$ results in an orthogonal representation~$\ogr$ of~$G$, as the rotation of the new face~$f$ is~$\rot(f)=\sigma(\ogr_1)-\sigma(\ogr_2)+0=2-2=4$. Moreover,~$\sigma(\ogr)=-1 + \sigma(\ogr_1)-1=0$ and every st-path in~$G$ has to either traverse~$e^s_1$ and~$e^t_1$ or~$e^s_2$ and~$e^t_2$ for which~$\lrefs{e^s_1}=r_1^s=-1,\ \lrefs{e^t_1}=-r_1^t=1,\ \lrefs{e^s_2}=r_2^s=1$, and~$\lrefs{e^t_2}=-r_2^t=-1$ hold. The existence of~$\ogr$ implies~$\slr=1$.
    
    For the ''$\implies$''-direction, let~$\slr=1$ and let~$\ogr$ be an orthogonal representation of~$G$ with spirality~$0$ containing both a positive and a negative relative label in every st-path. As~$\lrefs{e^s_1}=0$ and~$\lrefs{e^t_1}=\sigma(\ogr)=0$, these labels must be present in~$G_1$ and~$G_2$. If~$r_1^s$ is~$0$, then these edges also have the same labels relative to~$e^s_1$, and \cref{lem:2-leg-bgeq2IfBothPosAndNeg} implies~$b_1^r \geq 2$ and therefore~$2 \in \st{1}{0}$. If~$r_1^s$ is~$-1$, then~$\sigma(\ogr_1)\geq 1$ and every edge~$e$ with~$\lrefs{e}\geq 1$ now has~$\lref{s_1}{e}=\lrefs{e}-r_1^s\geq 2$. So~$1 \in \st{1}{2}$, which implies~$2 \in \st{1}{0}$. With the same argumentation using~$G_2$, also~$-2 \in \st{2}{0}$ follows.
\end{proof}

Different to \cref{sec:sp3graph2-leg}, the \structure{} of a graph now not only contains simple bounds, but the more complex bend step value~$s$. This changes the runtime of computing a \structure{}.

\begin{lemma}\label{lem:g2leg-poly-time}
    Given a 2-legged series-parallel rectilinear-plane 3-graph~$G$, a \structure{}~$[s,s^z,\slr]$ of $G$ can be computed in~$\bigO{n^2}$ time.
\end{lemma}
\begin{proof}
    A decomposition tree of~$G$ can be computed in linear time with~$\bigO{n}$ nodes. Per inner node~$\phi$, the calculation of~$\mstructuren{\phi}$ takes constant time for the zero step value~$s^z$ and the left-right step value~$\slr$. The time taken for calculating the bend step value~$s$ can be bounded by the number of sets in the codomain of~$s$ not being the empty set. As the in absolute terms highest relative label is proportional to the number of vertices~$n$ at which the label may change,~$s$ can be represented by at most~$2n$ sets that according to \cref{lem:g2leg-step-implications} are intervals. By only calculating the bounds of each interval in \cref{lem:g2leg-S-values,lem:g2leg-P-values}, the bend step value~$s$ can be calculated in~$\bigO{n}$ time. In total, the \structure{} of~$G$ can then be computed in~$\bigO{n^2}$ time.
\end{proof}