How to characterize the planar graphs in which every simple cycle can bound a face

Question

For convenience, say that a graph is very planar if for each simple cycle in the graph, there exists a planar embedding such that the cycle is the boundary of a face in the embedding. For example $K_4$ is not very planar because none of its $4$-cycles can be made to bound a face. On the other hand, $K_4\!-\!e$ is very planar: it has three simple cycles, and you can find a suitable embedding for each.

What are necessary and sufficient conditions to say that a graph is very planar? Is there a natural set of a obstructions (like in the context of the Robertson-Seymour Theorem) to a graph being very planar?

Answer 1

(Update: found the result that finishes the proof.)

The very planar graphs are precisely the graphs with no $K_4$ minor. (Incidentally, these are precisely the series-parallel graphs, though I sure don't see the connection.)

We begin by proving the following two results, which get us $90\%$ of the way there.

If a graph $G$ contains a subdivision of $K_4$, then it is not very planar.

Let $v_1, v_2, v_3, v_4$ be the vertices of $G$ such that there are disjoint paths from $v_i$ to $v_j$ for any $i \ne j$. Then the paths $v_1$ to $v_2$, $v_2$ to $v_3$, $v_3$ to $v_4$, and $v_4$ to $v_1$ form a cycle $C$ which I claim is not a face of any embedding.

If it were, we could choose an embedding in which $C$ is the outside face. But then the path from $v_1$ to $v_3$ divides $C$ into two parts, with $v_2$ and $v_4$ in different parts; they cannot be connected by a path that does not go outside $C$ or cross the path from $v_1$ to $v_3$.

If a graph $G$ is not very planar, then it contains a $K_4$ minor.

(Note: if a graph $G$ is not planar, then it has a $K_4$ minor, because both $K_5$ and $K_{3,3}$ have a $K_4$ minor. So I will assume that $G$ is planar, though not very planar.)

Let $C$ be a cycle of $G$ that cannot be turned into a face. If we removed the vertices of $C$ from $G$, we'd be left with the disjoint union of connected components $G_1, G_2, \dots, G_k$. We'll start with a planar embedding of just $C$ (which obviously has $C$ as a face), and add the components $G_1, \dots, G_k$ back in, one at a time, so that at each step, either:

• we continue to have a planar embedding with $C$ as a face, or
• we find a $K_4$ minor.

When we add $G_i$ back in, count how many vertices of $C$ have neighbors in $G_i$. If it is one or fewer, then we can always combine the current planar embedding of $C$ with a planar embedding of $G_i$, putting $G_i$ outside the face $C$. If it is three or more, then we can delete edges until it is three, delete components $G_1, \dots, G_{i-1}$, and contract $G_i$ to a point to be left with a subdivision of $K_4$, which is a $K_4$ minor. So the only interesting case is when only two vertices $v_1, v_2$ of $C$ have neighbors in $G_i$.

In that case, we can combine our planar embedding of $C$ with a planar embedding of $G_i$, putting $G_i$ outside $C$, provided we can draw a path from $v_1$ to $v_2$, outside $C$, without crossing any previous edges. This is possible, provided that no previous $G_j$, $j<i$, have had two neighbors $w_1, w_2$ on $C$ such that the path from $w_1$ to $w_2$ would cross the path from $v_1$ to $v_2$. But if that does happen, we can contract $G_i$ and $G_j$ to a point, throw away all other components, and also obtain a $K_4$ minor.

---

Normally it would be a problem to juggle subdivisions and minors the way I am doing, but it turns out that in the case of $K_4$, they are equivalent, by the following claim.

Let $H$ be a graph with maximum degree at most 3. Then $H$ is a minor of $G$ if and only if $G$ contains a subdivision of $H$.

There is some discussion of this claim on MSE here, with maybe a proof and maybe a source giving a proof, though the question I link to might deserve some more attention.