Collection of Maths Problems

Outerplanar graphs

Task number: 4061

• 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.