Planar Graph Explorer

Select a graph to start exploring planarity!

Learning Guide

Select a graph and start exploring to see learning insights here!

Graph Parameters

Graph Parameters

Graph Info

Vertices: 6

Edges: 0

Crossings: 0

Status: Unknown

Planar Graphs

Planar Graphs

• Can be drawn without edge crossings

• K₄ is planar (complete graph on 4 vertices)

• Cube graph is planar

• Drag vertices to find planar layout!

Non-Planar Graphs

• Cannot be drawn without crossings

• K₅ is non-planar (5 vertices, all connected)

• K₃,₃ is non-planar (bipartite, 3+3 vertices)

• Kuratowski's theorem applies

Planar Graphs

A planar graph can be embedded in the plane with no edge crossings.

Properties:

  • Can be drawn without edge intersections
  • Euler's formula: V - E + F = 2
  • For simple planar graphs: E ≤ 3V - 6
  • Every face is bounded by at least 3 edges

Examples:

Trees, cycles, wheels, and complete graphs K₁, K₂, K₃, K₄.

Non-Planar Graphs

Non-planar graphs cannot be drawn in the plane without edge crossings.

Key Examples:

  • K₅: Complete graph on 5 vertices
  • K₃,₃: Complete bipartite graph
  • Any graph containing K₅ or K₃,₃ subdivision
  • Utility graph (3 houses, 3 utilities)

Kuratowski's Theorem:

A graph is non-planar if and only if it contains a subdivision of K₅ or K₃,₃.

Testing Planarity

Interactive exploration helps build intuition for recognizing planar graphs.

Strategies:

  1. Start with outer face vertices
  2. Minimize edge crossings by repositioning
  3. Look for forbidden subgraphs
  4. Use Euler's formula to check necessity

Applications:

Circuit design, geographic mapping, network layout, and graph drawing algorithms.