2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Given that this is a challenge question, I strongly suggest you try to solve it yourself. Challenge questions are made to be tackled on one's own. $\endgroup$
    – Yuval Filmus
    Jan 31, 2014 at 21:02
  • $\begingroup$ Could I perhaps have a hint/push in the right direction for the missing case? $\endgroup$
    – user4734
    Jan 31, 2014 at 21:09
  • $\begingroup$ You're missing the point of challenge questions. These are questions meant to challenge yourself. The point is entirely missed unless you work it out yourself. Challenge yourself! If the instructor allows, perhaps you could discuss it with other students. This is more appropriate than an expert giving away the solution. $\endgroup$
    – Yuval Filmus
    Jan 31, 2014 at 21:15
  • $\begingroup$ I agree - But I am not asking to be given a solution... just a step in the right direction. $\endgroup$
    – user4734
    Jan 31, 2014 at 22:29

1 Answer 1

Reset to default
1
+100
$\begingroup$

The idea of the proof is to come up with a parameter of graphs $f(G)$ satisfying the following properties:

  1. The outerplanarity of $G$ is $O(f(G))$.
  2. 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)) & \text{if } f(G_1) \neq f(G_2), \\ \max(f(G_1),f(G_2)) + O(1) & \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) < 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)$.

Improve this answer
$\endgroup$
9
  • $\begingroup$ I appreciate the time you took to give me a hint, but I don't really know of any other parameters that could apply. The only things I know about k-outer-planarity and 2-terminal SP-graphs are the definitions above. I think that what I had written in my original post is somewhat similar to what you wrote as well, but I think for now I will keep working at it by working with outer-planarity directly :) $\endgroup$
    – user4734
    Feb 1, 2014 at 20:11
  • $\begingroup$ @Nizbel99 I added the definition of $f(G)$. Hopefully I got the definitions right and so everything works. $\endgroup$
    – Yuval Filmus
    Feb 5, 2014 at 2:56
  • $\begingroup$ I understand your solution up to the very last sentence (which is more or less where I was getting stuck in my solution as well). I can buy that argument when the newly added edge between both terminals does not go through the outside face in the "good embedding". But what if it does? I don't see how we can argue that the outerplanarity is $f(G_2)$. $\endgroup$
    – user4734
    Feb 5, 2014 at 4:27
  • $\begingroup$ Because if the line does not go through the outside face, when we peel off the first layer from $G$, we would be removing the entire first layer of $G_2$, and then getting at least two components, in which the one would have the required outerplanarity. But this argument doesn't hold when the line goes through the outerface. $\endgroup$
    – user4734
    Feb 5, 2014 at 4:34
  • 1
    $\begingroup$ On the contrary, when we peel off the first layer of $F(G)$, the entire first layer of $F(G_2)$ is peeled off. This is because replacing the extra edge with $F(G_1)$ "hides" the same vertices, while the two terminals are still on the outer face. This is not the case for $F(G_1)$, which now has a new outer edge from the other side, so we get $\max(f(G_2),f(G_1)+1) = f(G_2)$. $\endgroup$
    – Yuval Filmus
    Feb 5, 2014 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.