Плоский граф (планарный граф) — это граф, который можно изобразить на плоскости так, что никакие два его ребра не пересекаются нигде, кроме инцидентной им обоим вершины. 4

Некоторые критерии плоскостности:

• Теорема Ханани–Тутте. 1 Граф является плоским, если каждая независимая пара рёбер пересекается чётное число раз. 1
• Теорема Понтрягина — Куратовского. 2 Граф плоский, если он не содержит подграфа, гомеоморфного графу K5 или K3,3. 2

Некоторые свойства плоских графов:

• Формула Эйлера. 12 Если конечный, связный плоский граф нарисован на плоскости без каких-либо пересечений рёбер, то количество вершин минус количество рёбер плюс количество граней (областей, ограниченных рёбрами) равно 2. 1
• Максимально плоский граф. 1 Граф называется максимально плоским, если невозможно добавить к нему ни одного ребра так, чтобы новый граф был плоским. 3
• Спрямление графа. 5 Любой плоский граф можно перерисовать на плоскости так, что все его рёбра будут отрезками прямых. 5