Example of Planar graphs

 

Example of Planar Graphs

A planar graph is a graph that can be drawn on a plane without any edges crossing each other. If a graph can be redrawn to remove all crossings, it is planar.

---

Example 1: Triangle Graph ($K_3$)

A simple triangle graph with three vertices $A, B, C$ and three edges:

Graph Representation

css
    A
   / \
  B---C

• Since this graph can be drawn without edges crossing, it is planar.

---

Example 2: Square with a Diagonal

Consider a square with four vertices A, B, C, D, and an added diagonal AC:

Graph Representation

less
    A ----- B
    |  \    |
    |   \   |
    D ----- C

• This graph is still planar because no edges need to cross.

---

Example 3: Complete Graph $K_4$ (Planar Form)

A complete graph on four vertices (A, B, C, D) with every vertex connected to every other vertex.

• Normally, $K_4$ has a crossing, but it can be drawn without crossing edges by rearranging its layout:

Planar Drawing of $K_4$

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

• Since it is possible to redraw it without crossings, $K_4$ is planar.

---

Non-Planar Example: $K_5$ and $K_{3,3}$

1. The Complete Graph $K_5$ (five fully connected vertices) is non-planar.
2. The Bipartite Graph $K_{3,3}$ (three nodes connected to three other nodes) is also non-planar because it violates Kuratowski’s Theorem.

---

Applications of Planar Graphs

• Circuit Board Design (avoiding wire crossings)
• Geographical Maps (countries as regions, roads as edges)
• Network Topology (designing efficient road systems)

Planar graphs are essential in graph theory, computer science, and engineering!