Planar Graph | Sahithyan's Notes

A graph that can be drawn on a plane without any edges crossing.

Aka. planar embedding. A drawing of the graph without edge crossings. A graph can have 0 or 1 or more planar representations.

A region in the planar representation of a graph. Outer region of the graph is a single face.

Number of edges surrounding a face, in a planar representation of a graph. Greater than or equal to 3.

\sum {\text{fdeg} (f)} = 2|E| \ge 3 |F|

In case of bipartite graph: $2|E| \ge 4|F|$ .

Number of faces surrounding an edge, in a planar representation of a graph. Either 1 or 2.

Euler’s Formula

For a connected planar graph $G=(V,E)$ with $|V|=v$ and $|E|=e$ :

v - e + f = 2

Here $f$ is the number of faces.

For a disconnected graph with $k$ components, the equation becomes $v-e+f=k-1$ .

All planar representations of a graph has the same number of regions.

For a connected planar simple graph with $v \ge 3$ , the graph must satisfy $e \le 3v - 6$ .

Certain graphs cannot be drawn without edge crossings.

Examples:

$K_5$
Complete graph with 5 vertices. Does not satisfy the corollary of Euler’s formula for planar graphs, thus non-planar.
$K_{3,3}$
Complete bipartite graph with partitions of size 3. Satisfies the corollary of Euler’s formula, but is still non-planar. It can be shown that it contains a subgraph homeomorphic to $K_5$ .

These are the smallest non-planar graphs.

A graph is non-planar iff it contains a subgraph homeomorphic to $K_5$ or $K_{3,3}$ .