Planar networks

Question

Let $(b_1,...,b_n)$ be a sequence of positive integers. Define a $(b_1,...,b_n)$-network as the following graph $G$:

1. $V(G)=V_1\cup...\cup V_n$
2. $V_i\cap V_j=\emptyset$ ($1\leq i<j\leq n$)
3. $|V_i|=b_i$ ($1\leq i\leq n$)
4. $E(G)=\{\{u,v\}:u\in V_i,v\in V_{i+1} \text{ for some }i<n\}$

Example of the $(3,5,3)$-network:

It is straightforward that the condition $b_i\leq 2$ or $b_{i+1}\leq 2$ ($\text{for all }i<n$) is necessary for a $(b_1,...,b_n)$-network to be planar. Is it true that this is also the sufficient condition? If not, what the sufficient condition could be?

Answer 1

Here is a sufficient condition we can show.

Proposition. Consider $n\ge 3$ many positive integers $b_1 ,\ldots ,b_n$, where $b_i \le 2$ for all $i\neq 1,n$, and $b_1,b_n$ can be any positive integer. Then the $(b_1,\ldots ,b_n)$-graph is planar.

The idea is a graph is planar if and only if it is also planar on the sphere (that the edges can be untangled on the sphere). This can be seen by taking a stereographic projection. And being planar on the sphere is the same as being planar on any surface homeomorphic to the sphere, say a cylinder with tops. So to show this $(b_1,\ldots,b_n)$-graph satisfying those our conditions is planar, we just need to draw it without the edges crossing on the cylinder.

Indeed, the two ends of the graph can be easily made planar, and the inner parts we can wrap around the cylinder with the edges not crossing. A sketch is shown below:

Occasionally we have some $b_i = 1$, where $1<i<n$, but that is also easily seen to be not a problem for planarity.

Answer 2

Just as a reply to another answer

The explicit way to show the planarity of graphs from the @bonsoon's answer:

Answer 3

The answer to the first question is no due to the following theorem which gives the necessary and sufficient condition.

Theorem. Let $G$ be a $(b_1,...,b_n)$-network, then:

1. If $n=1$, then $G$ is planar
2. If $n=2$, then $G$ is planar iff $b_1\leq2\vee b_2\leq2$
3. If $n\geq3$, then $G$ is planar iff $\forall(1<i<n):b_i>2\rightarrow b_{i-1}=b_{i+1}=1$

Proof. The first case is obvious. In the second case, if the condition doesn't hold, then $G$ contains $K_{3,3}$ which is not planar. Otherwise, $G$ is a subgraph of a planar graph $K_{2,x}$ $(x\geq1)$. Consider the case $n\geq3$. Suppose that the condition doesn't hold. Then for some $1<i<n$ we have $b_i>2$ and at least one of $b_{i-1}$ or $b_{i+1}$ is greater than $2$. Again, this implies that $G$ contains $K_{3,3}$. Finally, let's prove by induction that the last condition is sufficient for $G$ to be planar.

Base case. Suppose $n=3$ and the condition holds. The cases when $b_2=1$ or $b_1=b_3=1$ are straightforward. Now, if $b_2=2$, then $G$ is just $K_{2,b_1+b_3}$ which is planar.

Induction step. Suppose $G$ is a $(b_1,...,b_{n+1})$-network and the condition holds for $n$ ($n\geq3$). Then the condition $b_i>2\text{ }(1<i<n+1)\rightarrow b_{i-1}=b_{i+1}=1$ implies the $(b_1,...,b_n)$-network $G'$ is planar. There are two cases:

1. $b_{n+1}\geq2$. We have $b_n\leq2$. If $b_n=1$, then it's obvious how to use $G'$ to draw $G$ on a plane. Assume $b_n=2$. Then we have $b_{n-1}\leq2$. If $b_{n-1}=2$, consider the sets $V_{n-1}=\{u_1,u_2\}$ and $V_{n}=\{u_3,u_4\}$ from the definition. When drawn on a plane, $G'$ contains a face $F$ that is the cycle $u_1-u_3-u_2-u_4-u_1$. We can draw $G$ planarly putting $b_{n+1}$ vertices inside of $F$. If $b_{n-1}=1$, then both vertices from $V_n$ in $G'$ have the degree $1$, and it's straightforward to draw $G$ on a plane.

2. $b_{n+1}=1$. If $b_n>2$, then $b_{n-1}=1$ and all the vertices from $V_n$ in $G'$ have the degree $1$, so $G$ can be drawn on a plane. The case $b_n\leq2$ is analogous to the previous step.

$\blacksquare$

The following picture demonstrates why $(2,3,2)$-network can not be planar: