Гамма-алгоритм

Задача:

Определить, является ли граф планарным, и, если да, произвести его плоскую укладку.

Существует теорема Понтрягина-Куратовского, которая говорит, что граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных [math] K_{5} [/math] или [math] K_{3, 3} [/math]. Но этот критерий очень трудно проверить на практике, поэтому данная теорема представляет лишь теоретический интерес.

Чтобы проверить планарность графа и произвести его плоскую укладку, удобно пользоваться гамма-алгоритмом.