Planarity criteria

Planarity criteria --- критерии планарности.

The following three planarity criteria are classical.

1. Kuratowski's criterion. A graph [math]\displaystyle{ G }[/math] is planar if and only if it does not contain a subdivision of [math]\displaystyle{ K_{5} }[/math] or [math]\displaystyle{ K_{3,3} }[/math].

Another name is Pontrjagin-Kuratowski's criterion.

2. Whitney's criterion. A graph [math]\displaystyle{ G }[/math] is planar if and only if it has a combinatorial dual graph [math]\displaystyle{ G^{\ast} }[/math].

3. MacLane's criterion. A graph [math]\displaystyle{ G }[/math] is planar if and only if it has a cycle basis such that each edge of [math]\displaystyle{ G }[/math] belongs to at most two circuits of the basis.