## Outerplanar graphs

Prove that a graph is outerplanar if and only if it does not contain a subdivision of $$K_4$$ nor of $$K_ {2{,}3}$$ as a subgraph.

A graph is outerplanar if it has a planar drawing such that all vertices are incident with the outer face.

• #### Hint

Add an apex vertex (a vertex connected to all the others) and reduce the problem to planarity.

• #### Solution

Let’s have a graph $$G$$ that does not contain $$K_4$$ nor $$K_ {2{,}3}$$. We make a graph $$G’$$ by adding one new vertex $$v$$ to $$G$$ connected by an edge to all the others. The graph $$G’$$ does not contain subdivisions $$K_5$$ nor $$K_ {3{,}3}$$. Therefore, it is planar and we can draw it so that $$v$$ is incident with the outer face. Then just remove $$v$$ and we get a drawing of an outer planar drawing of $$G$$, because each vertex will be incident with the outer face.

We show the other implication. Let us have an outerplanar graph $$G$$. We want to show that it does not contain the subdivision of $$K_4$$ nor of $$K_{2{,}3}$$. Let for a contrary such a subdivision exist. Take the outerplanar drawing $$G$$ and add to the outer face the vertex $$v$$ adjacent with all vertices of the graph $$G$$. The resulting graph will be planar. In addition, it will contain a subdivision of $$K_5$$ or of $$K_{3{,}3}$$ and this is a contradiction with Kuratowski theorem, that planar graphs do not contain subdivisions of $$K_5$$ nor of $$K_{3{,}3}$$.

• #### Variant

Prove the above characterization of outerplanar graphs without using Kuratowski’s theorem.

• #### Solution

Forward implication: neither $$K_4$$ nor $$K_ {2{,}3}$$ can be drawn in the outerplanar way, because the outer cycle always separates the remaining vertex.

Replacing paths with edges preserves outerplanarity. If the subdivision of $$K_4$$ was outerplanar, the $$K_4$$ itself would be outerplanar. Similarly for $$K_{2{,}3}$$. Therefore, an outerplanar graph cannot have a subdivision of $$K_4$$ nor of $$K_{2{,}3}$$.

We can prove the backward implication by induction according to the number of edges. Joining outerplanar drawings by a bridge or by an articulation preserves the outerplanarity. Without loss of generality, we can restrict ourselves to two-connected graphs. These can be created from cycles by adding ears.

The basis of induction, cycles, are outerplanar.

We find in the $$G$$ an ear. According to the inductive hypothesis, $$G$$ without the ear has an outerplanar drawing. Because this graph is two-connected, the outer face is surrounded by a cycle. The following cases may occur:

• The ear is of length at least two and connects two adjacent vertices of the cycle, then we draw it to the outside this edge.
• The ear is of length at least two and connects the non-adjacent vertices of the cycle, then $$G$$ has a subdivision of $$K_ {2{,}3}$$ and therefore this cannot happen.
• The ear is an edge and connects two non-adjacent vertices of the cycle from the same inner face, then we draw it into this face.
• The ear is an edge and connects two non-adjacent vertices of the cycle in different inner faces, then $$G$$ has a subdivision of $$K_4$$ and therefore this cannot happen.