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.