577
правок
Изменения
→проверка
Итоговая асимптотика алгоритма {{---}} <tex>O(\log{n})</tex>.
= проверка Гамма-алгоритм ={{Задача|definition=Определить, является ли граф планарным, и, если да, произвести его плоскую укладку.}}Существует [[Теорема Понтрягина-Куратовского|теорема Понтрягина-Куратовского]], которая говорит, что граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных <tex> K_{5} </tex> или <tex> K_{3, 3} </tex>. Но этот критерий очень трудно проверить на практике, поэтому данная теорема представляет лишь теоретический интерес.
