Planar Graphs

A graph is planar if it can be embedded in the plane without any edges crossing. Such a drawing is called a plane embedding. In a plane embedding, the edges divide the plane into regions called faces, including the outer (infinite) face.

Important properties

• Planarity is a property of the abstract graph, not just a particular drawing.

• A plane graph is a specific drawing of a planar graph with no edge crossings.

• Euler's formula relates the number of vertices ($V$), edges ($E$), and faces ($F$) in a connected plane graph: $V - E + F = 2$.

• Subdividing edges (replacing an edge with a path) preserves planarity.

• Adding edges may destroy planarity if it forces crossings.