Алгоритмы распознавания планарности графов. А. Д. Рябичев

Как многие вероятно догадываются, задача «планарен ли заданный граф» имеет алгоритмическое решение. Мы разберёмся, как именно её решать, и как ускорить алгоритм до полиномиального с использованием интересной техники, приходящей из алгебраической топологии. Она позволяет таким же образом решать некоторые многомерные обобщения задачи про графы, а другие, открытые до сих пор, не позволяет, и об этом мы тоже поговорим, если позволит время.
Участникам предлагается реализовать на компьютере алгоритм (или несколько разных алгоритмов) распознавания планарности графов, а также попробовать визуализировать результат.
ryabichev@179.ru
ryabichev@179.ru
ryabichev@179.ru