МОДИФІКАЦІЯ МЕТОДУ НИТЕЙ С ВИКОРИСТАННЯМ ГАМА АЛГОРИТМУ ДЛЯ ПОБУДОВИ ТОПОЛОГИЧНОГО МАЛЮНКУ ГРАФУ
DOI:
https://doi.org/10.32782/tnv-tech.2024.1.10Ключові слова:
граф, перевірка планарности, візуалізація графів, топологічний малюнок графа, діаграма обертання вершин, ізометричні цикли, метод нитей, обертання вершин графа, алгоритмАнотація
В цій роботі розглядається модифікований алгоритм методу ниток, призначений перевірки графа на планарність з одночасним побудовою топологічного малюнка плоского графа як системи ізометричних циклів і списків обертання вершин графа. Отримання обертання вершин графа одразу вирішує дві найважливіші задачі: завдання перевірки графа на планарність та завдання побудови топологічного малюнка плоского графа. Отримана в результаті роботи алгоритму система ізометричних циклів графа індукує обертання вершин опису топологічного малюнка плоского графа з метою подальшої візуалізації. Топологічний малюнок плоскої частини графа дозволяє описувати процес планаризації методами алгебри, не виробляючи ніяких геометричних побудов на площині. Представлений алгоритм заснований на розбудові опорного циклу та побудові списку зворотних маршрутів. Основою розрахунку є побудова матриці фундаментальних циклів на підставі побудови остовного дерева графа методом пошуку в глибину. З матриці фундаментальних циклів проводися виділення ланцюгів, які утворюють маршрути. Для отримання системи ізометричних циклів використовують вбудовування маршрутів за допомогою модифікованого гамма алгоритму. Адаптована версія гамма алгоритму у додатку методу ниток дозволяє вбудовувати в цикли графа утворюють маршрути ланцюга та спрощує завдання пошуку відповідних для цього циклів. Адаптація гамма алгоритму включає додатковий прогностичний індекс визначення можливості вбудовування в даний цикл наступних шляхів. Планаризация графів є найважливішим підзавданням під час вирішення безлічі актуальних прикладних завдань, як-то проектування складних виробів і систем, плоских конструктивів, аналіз соціальних мереж та інших.
Посилання
Goyal P., Ferrara E. Graph embedding techniques, applications, and performance: A survey. Knowledge-Based Systems. 2018. Vol. 151. P. 78–94.
Tamassia R. Handbook of Graph Drawing and Visualization. C&H/CRC. 2013. P. 844.
Kurapov S. V., Davidovsky M. V., Tolok A. V. Generating a topological drawing of the flat part of a non-planar graph. Scientific Visualization. 2020. Vol. 12, No. 1, P. 90–102. DOI: 10.26583/sv.12.1.08
Kavitha T., Liebchen C., Mehlhorn K., Michail D., et al. Cycle bases in graphs – characterization, algorithms, complexity, and applications. Comput. Sci. Rev.. 2009. No. 3. P. 199–243.
Ringel G. Map Color Theorem. Repr. of the orig. 1st ed. (1974). Springer. 2011. P. 212.
Patrignani M. Planarity testing and embedding. Chapter 1. Handbook of Graph Drawing and Visualization. Roberto Tamassia, Editor. CRC Press. 2013. June 24, P. 1–42.
Hopcroft J., Tarjan R. E. Efficient planarity testing. Journal of the Association for Computing Machinery. 1974. Т. 21, No. 4, P. 549–568.
Kurapov S. V., Davidovsky M. V., Tolok A. V. A modified algorithm for planarity testing and constructing the topological drawing of a graph. The thread method. Scientific Visualization. 2018. Т. 10, No. 4, P. 53–74.
Hrebeniuk B. Modification of the analytical gamma-algorithm for the flat layout of the graph. Computer Science & Software Engineering. 2018. Vol. 2292, P. 46–54.
