Эволюционный алгоритм для проверки планарности графов

В работе рассматривается приближенный алгоритм проверки планарности графов. В процессе работы алгоритма строится изображение графа c минимальным количеством пересечений рёбер. Алгоритм эффективно решает перечисленные задачи. Можно сделать обобщенный вывод о том, что эволюционный алгоритм эффективен для решения оптимизационных задач геометрии. Вычислительная сложность алгоритма определяется как , где – количество итераций алгоритма, – размер популяции (задаётся пользователем), – количество рёбер графа.[1]

https://habr.com/ru/articles/843342/

#граф #планарность #визуализация_графа #алгоритмы_на_графах #эволюционный_алгоритм #генетические_алгоритмы