How to show that all 2-terminal SP-graphs are O(log n)-outer-planar
The idea of the proof is to come up with a parameter of graphs $f(G)$ satisfying the following properties:


The outerplanarity of $G$ is $O(f(G))$.
If $G$ is the (serial or parallel) composition of two graphs $G_1,G_2$, then
$$ f(G) \leq \begin{cases} \max(f(G_1),f(G_2)) &amp; \text{if } f(G_1) \neq f(G_2), \\
\max(f(G_1),f(G_2)) + O(1) &amp; \text{if } f(G_1) = f(G_2). \end{cases} $$


If we are able to construct such a parameter, then your result follows (exercise). It could be that outerplanarity itself satisfies these axioms, but this is not clear. I was able to construct another parameter $f(G)$ which does satisfy these properties, and is very similar to the outerplanarity of $G$. Can you?



Here is my solution. For a two-terminal graph $G$, let $F(G)$ be the result of adding an extra edge connecting both terminals, and define $f(G)$ to be the outerplanarity of $F(G)$, when the extra edge is forced to be on the outer face. Clearly the outerplanarity of $G$ is at most $f(G)$.

It is easy to see that if $G$ is the serial composition of $G_1,G_2$ then $f(G) = \max(f(G_1),f(G_2))$. Now suppose that $G$ is the parallel composition of $G_1,G_2$. It is easy to see that $f(G) \leq \max(f(G_1),f(G_2)) + 1$. This is not good enough, however: we need to show that when $f(G_1) &lt; f(G_2)$, then $f(G) = f(G_2)$ (without the $+1$). To that end, take a "good" planar embedding of $F(G_2)$ (with outerplanarity $f(G_2)$), and replace the extra edge with a copy of a "good" planar embedding of $F(G_1)$ (with outerplanarity $f(G_1)$). The result is a planar embedding of $F(G)$ with outerplanarity $f(G_2)$.