Planar Graphs

Planar Graphs

In graph theory, a planar graph is a graph that can be drawn on a plane (or a flat surface) such that no edges cross each other. In other words, a graph is planar if it is possible to lay out its vertices and edges on a two-dimensional surface without any edges intersecting, except at their endpoints (the vertices).

Planar graphs have important applications in areas like circuit design, geographical mapping, and graph drawing. Understanding planar graphs is crucial in graph theory, and several fundamental concepts and results are associated with them.

1. Definition of a Planar Graph

A graph $G = (V, E)$ is planar if there exists an embedding of $G$ into the plane, i.e., a way to draw $G$ on the plane such that no two edges intersect except at their vertices.

2. Non-Planar Graphs

If a graph cannot be drawn on a plane without edges crossing, it is called a non-planar graph. One of the most famous examples of a non-planar graph is the K5 (complete graph on 5 vertices) and K3,3 (complete bipartite graph on two sets of 3 vertices).

3. Kuratowski's Theorem

A key result in the theory of planar graphs is Kuratowski's Theorem, which characterizes planar graphs in terms of subgraphs.

• Kuratowski's Theorem states that a graph is planar if and only if it does not contain a subgraph that is a subdivision of either K5 (the complete graph on 5 vertices) or K3,3 (the complete bipartite graph on two sets of 3 vertices).

K5 (Complete graph on 5 vertices)

• The graph K5 is a complete graph on 5 vertices, meaning each vertex is connected to every other vertex.
• K5 cannot be drawn in a plane without edges crossing.

K3,3 (Complete bipartite graph on two sets of 3 vertices)

• K3,3 is a complete bipartite graph consisting of two sets of 3 vertices, with each vertex in one set connected to all vertices in the other set.
• K3,3 also cannot be drawn in a plane without edges crossing.

Thus, Kuratowski's Theorem provides a way to check whether a graph is planar: if the graph contains a subgraph that is a subdivision of K5 or K3,3, it is non-planar.

4. Euler’s Formula for Planar Graphs

One of the most important results for planar graphs is Euler's formula, which relates the number of vertices ($V$), edges ($E$), and faces ($F$) in a planar graph.

Euler's formula states that for a connected planar graph:

Where:

• $V$ is the number of vertices,
• $E$ is the number of edges, and
• $F$ is the number of faces (regions, including the outer region, into which the plane is divided by the edges).

Applications of Euler's Formula

• Planarity Checking: Euler’s formula is useful for determining whether a given graph can be planar based on its number of vertices and edges. If a graph does not satisfy Euler's formula, it cannot be planar.
• Graph Drawing: Euler’s formula can help in understanding the constraints of drawing planar graphs and helps in algorithms for planar graph drawing.

5. Planar Graphs and Graph Coloring

In planar graphs, there is a well-known result called the Four Color Theorem, which states that:

• Any planar graph can be colored using no more than four colors such that no two adjacent vertices share the same color.

This result was first conjectured in 1852 and was proven in 1976 by Kenneth Appel and Wolfgang Haken, using computer-assisted proof methods. The Four Color Theorem has important implications for map coloring, where regions of a map can be represented as vertices, and borders between regions as edges.

6. Planar Graph Drawing

• Planar Embedding: The process of embedding a planar graph into the plane such that no edges intersect except at their endpoints is called a planar embedding.
• Face: In a planar embedding of a graph, the regions formed by the edges are called faces (including the outer face, which is the region surrounding the graph).

7. Properties of Planar Graphs

• Maximum number of edges: For a connected planar graph with $V$ vertices, the maximum number of edges $E$ is given by:

  $$E \leq 3V - 6$$

  This inequality holds for planar graphs with $V \geq 3$. If a graph exceeds this number of edges, it is non-planar.

• Planar Subgraphs: If a graph is planar, then every subgraph of it is also planar. However, the reverse is not necessarily true (i.e., not every subgraph of a planar graph is planar).

8. Types of Planar Graphs

• Outerplanar Graph: A graph is outerplanar if it can be embedded in the plane in such a way that all of its vertices lie on the boundary of the outer face.
• Polyhedral Graph: A polyhedral graph is a planar graph that represents the vertices and edges of a convex polyhedron (3-dimensional object). A classical example of a polyhedral graph is the graph of the tetrahedron or cube.

9. Applications of Planar Graphs

• Geographical Mapping: Planar graphs are used in geographical mapping and map coloring problems, where regions are represented by vertices, and borders between regions are represented by edges.
• Circuit Design: In electrical engineering, planar graphs are used to represent circuit layouts, ensuring that connections between components do not cross each other.
• Network Design: Planar graphs are useful in network topology, where the goal is to design a network that minimizes edge crossings.

Summary of Key Points

• A planar graph can be drawn on a plane without edge crossings.
• Kuratowski's Theorem helps identify non-planar graphs by checking for subgraphs isomorphic to K5 or K3,3.
• Euler's formula for a connected planar graph is $V - E + F = 2$.
• The Four Color Theorem guarantees that four colors are sufficient to color any planar graph.
• Planar graphs have limitations on the number of edges, given by $E \leq 3V - 6$.
• Applications: Planar graphs are used in map coloring, circuit design, network topology, and more.