How to show that all 2-terminal SP-graphs are O(log n)-outer-planar I am trying to show that every 2-terminal SP-graph is $O(\log(n))$-outer-planar for a challenge question on my assignment. In particular, I am trying to prove this by induction on the number of combinations (either a series or a parallel combination). This is what I have so far.

The base case on $0$ combinations is that we just have some edge $(s, t)$. Clearly this is outer-planar and so $O(\log(n))$-outer-planar as well (in this case, $\log(2) = 1$, so this does hold).

Now we do the inductive step. Given some 2-terminal outer-planar graph $G = (V, E)$, we will show that it is $O(\log(n))$-outer-planar, where $|V| = n$. Since $G$ is a 2-terminal outer-planar graph, it was either the result of combining two graphs $G_1$ on $n_1$ vertices and $G_2$ on $n_2$ vertices by series or by parallel. So we have two cases two consider.

The first case is when $G_1$ and $G_2$ were combined by series. By induction, $G_1$ is $O(\log(n_1))$-outer-planar and $G_2$ is $O(\log(n_2))$-outer-planar. Since $G$ was combined by series, it has $n = n_1 + n_2 - 1$ vertices, where $n_1, n_2 \ge 2$. Let $n_0 = \max(n_1, n_2)$. Then $G$ is $O(\log(n_0))$-outer-planar since we have not added any layers to $G_1$ or $G_2$ by combining them. It follows that $G$ is $O(\log(n))$-outer-planar since $n_0 \le n$.

In the second case, $G_1$ and $G_2$ are combined in parallel, meaning that $G$ has $n = n_1 + n_2 - 2$ vertices. Again by induction, $G_1$ is $O(\log(n_1))$-outer-planar and $G_2$ is $O(\log(n_2))$-outer-planar. However, this time we cannot conclude that the number of layers around $G$ is the same.

This is where I am stuck. I understand that we are at-most doubling the amount of vertices in $G$ by combining them in parallel, but I don't know how to use that to argue that the number of layers in $G$ is $O(\log(n))$. Any help would be appreciated since I've been stuck on this for several days now.

EDIT: Now that the deadline has passed for my assignment, I would love to have a solution so that I can prepare for my midterm exam (solutions to bonus/challenge problems are never posted).

Terminology

Series-parallel graphs (SP-graphs) are constructed in the following way. A two-terminal graph is a graph with two distinguished nodes $s,t$. A single edge connecting $s$ and $t$ is an SP-graph. If $(G_1,s_1,t_1)$ and $(G_2,s_2,t_2)$ are two SP-graphs, then their serial composition is an SP-graph, and their parallel composition is an SP-graph. The serial composition is obtained by identifying $t_1$ with $s_2$; the new terminals are $s_1$ and $t_2$. The parallel composition is obtained by identifying $s_1$ and $s_2$, and $t_1$ and $t_2$; the new terminals are $s_1=s_2$ and $t_1=t_2$. SP-graphs are the minimal class of graphs generated by these operations. See Wikipedia for more on this class.

$k$-outerplanar graphs: A planar embedding (i.e. an embedding without crossings) is $1$-outerplanar if all of the vertices belong to the unbounded face. For $k \gt 1$, a planar embedding is said to be $k$-outerplanar if removing the vertices on the outer face results in a $(k − 1)$-outerplanar embedding. A graph is $k$-outerplanar if it has a $k$-outerplanar embedding.
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)$.