Як перевірити граф на Планарність?

Визначення. Граф називається планарним, якщо його можна укласти на площині. Визначення. Граф називається плоским, якщо він покладений на площині.

В теорії графів товщина графа G – це найменша кількість плоских підграф, на які можна розкласти ребра графа G. Тобто якщо існує набір k плоских графів, що мають однаковий набір вершин, об'єднання яких дає граф G, то товщина графа G не більше за k. Таким чином, плоский граф має товщину 1.

Відповідний граф, складений з точок простору і кривих жорданових з , називають укладанням вихідного графа. Визначення: Граф називається планарним (англ. planar graph), якщо він має укладанням на площині.