Planar graph

A planar graph is a type of graph that can be drawn on a flat surface (like a piece of paper) without any of its edges crossing each other (except at the vertices, I suppose).

Planar graph: a graph which can be drawn so that no edges cross.

Euler’s formula

For any connected planar graph, there is a relationship between the number of vertices (V), edges (E), and faces (F) of the graph:

V - E + F = 2

Where:

• V = number of vertices
• E = number of edges
• F = number of faces (including the outer, infinite face)

This is Euler’s formula for planar graphs.

Kuratowski’s theorem

Kuratowski’s theorem is a way of telling whether a graph is planar or not.

A graph is non-planar only if it contains a subgraph that is a subdivision of either K_5 or K_{3,3}