Planarity in Graphs

Planarity in Graphs

In graph theory, a graph is considered planar if it can be embedded in the plane (i.e., drawn on a flat surface) such that no edges intersect or cross each other except at their endpoints. Essentially, a planar graph is a graph that can be drawn without any edges crossing, where each vertex is represented as a point and each edge as a curve connecting two points.

Key Concepts Related to Planarity:

1. Planar Graph: A graph is planar if it can be drawn on a plane without any of its edges crossing.
2. Non-Planar Graph: A graph is non-planar if it cannot be drawn on a plane without edge crossings.
3. Embedding: The process of drawing a graph in the plane, where an embedding ensures no edges cross each other except at vertices.
4. Faces: In the context of planar graphs, the regions formed by edges, including the outer infinite region, are called faces. A planar graph divides the plane into a number of regions (faces).

Key Properties of Planar Graphs:

• Euler's Formula: Euler's formula is a fundamental result in planar graph theory, which states that for any connected planar graph, the following relationship holds:

  $$V - E + F = 2$$

  where:

  • $V$ is the number of vertices,
  • $E$ is the number of edges,
  • $F$ is the number of faces (regions formed by edges, including the outer region).

  This formula provides an important check for whether a graph can be planar. If a graph satisfies this formula for its number of vertices, edges, and faces, it is likely planar.

Kuratowski’s Theorem

A fundamental result for identifying non-planarity is Kuratowski's Theorem, which provides a criterion for determining whether a graph is non-planar. According to this theorem:

• A graph is non-planar if and only if it contains a subgraph that is a subdivision of either:
  • K₅: The complete graph on 5 vertices (a graph where every pair of distinct vertices is connected by a unique edge).
  • K₃,₄: The complete bipartite graph between 3 and 4 vertices (a graph where the vertices are divided into two disjoint sets, and every vertex in one set is connected to every vertex in the other set).

In other words, if a graph contains a subgraph that can be transformed into $K_5$ or $K_{3,4}$ through edge contractions (subdividing edges into multiple edges), the graph is non-planar.

Planarity Testing:

To determine if a graph is planar, you can use several methods:

1. Drawing the Graph: This is the simplest but most tedious method, where you attempt to draw the graph in the plane without edge crossings. If successful, the graph is planar.

2. Kuratowski’s Theorem: As mentioned earlier, you check if the graph contains a subgraph that is a subdivision of $K_5$ or $K_{3,4}$. If such a subgraph exists, the graph is non-planar.

3. Planarity Algorithms: There are efficient algorithms to test planarity, such as:

   • The Hopcroft-Karp Algorithm: A planarity testing algorithm with linear time complexity, used to check if a graph is planar or not.
   • The Boyer-Myrvold Algorithm: An algorithm that tests planarity in linear time and constructs an embedding if the graph is planar.

Planar Graphs and Embeddings:

If a graph is planar, it means there exists at least one way to embed it in the plane without edges crossing. The embedding represents the graph's layout on a plane. Here are a few important concepts regarding planar embeddings:

• Face: A face is a region bounded by edges in a planar graph, including the outer infinite region.
• Dual Graph: The dual of a planar graph is another graph where each face of the original graph is represented by a vertex, and two vertices in the dual graph are connected by an edge if and only if their corresponding faces in the original graph are adjacent.
• Crossing Number: The crossing number of a graph is the minimum number of edge crossings required in any embedding of the graph in the plane.

Examples of Planar and Non-Planar Graphs:

1. Planar Graph:

   • Cycle Graph $C_4$ (a square) is planar because it can easily be drawn in the plane without any edges crossing.
   • Tree: Any tree is planar because there is no cycle, and thus, there is no possibility of edge crossings.

2. Non-Planar Graph:

   • $K_5$ (Complete graph on 5 vertices) is non-planar because it cannot be drawn in the plane without edges crossing. It is the simplest non-planar graph.
   • $K_{3,4}$ (Complete bipartite graph between 3 and 4 vertices) is also non-planar by Kuratowski's Theorem.

Applications of Planarity:

1. Geographical Mapping: Planar graphs are used to model maps where the vertices represent regions (such as countries or states), and the edges represent borders between regions. The goal is to color the map with the minimum number of colors such that no two adjacent regions share the same color (this is related to the Four Color Theorem).

2. Circuit Design: Planar graphs are important in circuit design, especially when designing electronic circuits on a flat surface, as the layout should avoid overlapping wires.

3. Network Layout: Planar graphs can be used to model the layout of communication networks where physical constraints require a planar arrangement of nodes and edges.

Conclusion

A graph is planar if it can be embedded in the plane without any edges crossing each other, and Kuratowski’s Theorem helps identify non-planar graphs by checking for subdivisions of $K_5$ or $K_{3,4}$. The Euler’s Formula provides an essential relationship between vertices, edges, and faces in planar graphs. Planarity testing algorithms help efficiently determine if a graph is planar, which is crucial in areas such as circuit design, map coloring, and network layout.