Некоторые графы нельзя представить на плоской поверхности из-за наличия определённых подграфов, согласно теореме Понтрягина — Куратовского. 12

Согласно этой теореме, если граф содержит подграф, гомеоморфный полному графу из пяти вершин (K5) или графу «домики и колодцы» (K3,3), то его невозможно разложить на плоскости. 12

Кроме того, есть необходимое условие: если граф непланарный, то он должен содержать больше 4 вершин, степень которых больше 3, или больше 5 вершин степени больше 2. 12

Пример графа, который нельзя уложить на плоскость, — полный двудольный граф с тремя вершинами в каждой из долей (K3,3). 2