49493

Автор(ы): 

Автор(ов): 

3

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Модифицированный алгоритм проверки планарности графа и построение топологического рисунка. Метод нитей.

Электронная публикация: 

Да

ISBN/ISSN: 

ISSN 2079-3537

DOI: 

10.26583/sv.10.4.05

Наименование источника: 

  • Научная визуализация

Обозначение и номер тома: 

Т. 10, № 4

Город: 

  • Москва

Издательство: 

  • МИФИ

Год издания: 

2018

Страницы: 

53-74
Аннотация
В данной работе рассматривается модифицированный алгоритм проверки графа на планарность с одновременным построением математических структур для описания топологического рисунка плоского графа. В качестве таких математических структур рассматриваются изометрические циклы и вращение вершин графа. Получение вращения вершин графа сразу решает две важнейшие задачи: задачу проверки графа на планарность и задачу построения топологического рисунка плоского графа. Полученная в результате работы алгоритма система изометрических циклов графа индуцирует вращение вершин для описания топологического рисунка плоского графа с последующей его визуализацией. Топологический рисунок плоской части графа позволяет описывать процесс планаризации алгебраическими методами, не производя никаких геометрических построений на плоскости. Представленный алгоритм основан на перестройке опорного цикла и построении блоков обратных маршрутов. Основой расчёта является выделение DFS-дерева графа (методом поиска в глубину). Визуализация планарных графов является важнейшей подзадачей при решении множества актуальных прикладных задач, таких как проектирование сложных изделий и систем, плоских конструктивов, анализ социальных сетей и др. Вычислительная сложность алгоритма определяется как O(m) = f1(m) + f2(m), где m – количество рёбер графа.

Библиографическая ссылка: 

Толок А.В., Курапов С.В., Давидовский М.В. Модифицированный алгоритм проверки планарности графа и построение топологического рисунка. Метод нитей. // Научная визуализация. 2018. Т. 10, № 4. С. 53-74.