Дата публикации: 2016

Дата публикации в реестре: 2020-03-03T19:21:49Z

Аннотация:

Рассматривается алгоритм проверки графа на планарность с одновременным построением математических структур для описания топологического рисунка плоского графа. Такими математическими структурами являются изометрические циклы и вращение вершин графа. Показано, что система изометрических циклов графа индуцирует вращение вершин для описания топологического рисунка плоского графа. В отличие от классических алгоритмов проверки планарности, например алгоритма Хопкрофта — Тарьяна, полученный в результате работы алгоритма топологический рисунок используется для визуализации плоского графа. Вычислительная сложность алгоритма определяется как O(m2), где m — количество рёбер графа.

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2016. № 2. С. 100-114