Planar Graphs and Kuratowski's Theorem Explained

What is a Planar Graph?

A planar graph is a graph that can be drawn on a plane without any edges crossing each other. This property is fundamental in graph theory, as it allows us to visualize complex relationships in a simpler way.

Key Characteristics of Planar Graphs:

• Vertices: The points where edges meet.
• Edges: The lines connecting the vertices.
• Faces: The regions bounded by edges (including the outer infinite region).

• Euler’s Formula: For a connected planar graph, the relationship between vertices (V), edges (E), and faces (F) is given by:

  V - E + F = 2

Example of a Planar Graph

Consider the following graph:

   A
  / \
 B---C
  \ / \
   D   E

In this graph:

• Vertices: A, B, C, D, E (5 vertices)
• Edges: (A, B), (A, C), (B, C), (B, D), (C, E), (D, E) (6 edges)
• Faces: 3 (the regions formed by the edges)

Applying Euler’s Formula

Using Euler’s formula:

• V = 5
• E = 6
• F = 3
• Calculation: 5 - 6 + 3 = 2, which confirms that this graph is planar.

Kuratowski’s Theorem

Kuratowski’s Theorem states that a finite graph is non-planar if and only if it contains a subgraph that is a subdivision of either the complete graph K5 (5 vertices, each connected to every other vertex) or the complete bipartite graph K3,3 (two sets of 3 vertices, where each vertex in one set is connected to all vertices in the other set).

Example of Non-Planar Graphs

1. The Complete Graph K5:

    A
   /|\
  / | \
 B--C--D
  \ | /
   \|/
    E

• This graph has 5 vertices and every vertex is connected to every other vertex. It cannot be drawn in a plane without edges crossing.

2. The Complete Bipartite Graph K3,3:

   A       D
   |\     /|
   | \   / |
   |  \ /  |
   B---C---E
   | / \   |
   |/   \  |
   C       F

• This graph consists of two sets of vertices, {A, B, C} and {D, E, F}, with every vertex in the first set connected to every vertex in the second set. It also cannot be drawn without edge intersections.

Summary

Understanding planar graphs and Kuratowski’s Theorem is essential for anyone studying graph theory. By identifying whether a graph can be drawn without crossings and recognizing the significance of K5 and K3,3, you can determine the planarity of various graphs.

Conclusion

In this article, we covered the definition and characteristics of planar graphs, provided practical examples, and discussed Kuratowski’s Theorem. This foundational knowledge will aid you in further exploring the intricate field of graph theory.