В теории может быть применен критерий Понтрягина-Куратовского об эквивалентности планарности графа и отсутствия в нем подграфов, гомеоморфных (или же стягиваемых) полному

или двудольному

.
На практике, для проверки планарности графа и для укладки его на плоскость хорош т.н. гамма-алгоритм.