In this article we present a new graph planarity testing algorithm along with the construction of mathematical framework used for representing topological drawings of plane graphs. This mathematical framework is based on the notions of graph isometric cycles and rotation of graph vertices. It is shown that the system of isometric cycles of a graph induces the rotation of its vertices for representing topological drawing of the plane graph. In contrast to the classical planarity testing algorithms, e. g. the Hopcroft - Tarjan algorithm, the topological drawing obtained as a result of the proposed algorithm execution is used subsequently for the visualization of the planar graph. Computational complexity of the proposed algorithm is estimated by O(m), where m is the number of edges in the graph.
Download file
Counter downloads: 547
- Title Planarity testing and constructing the topological drawing of a plane graph (DFS)
- Headline Planarity testing and constructing the topological drawing of a plane graph (DFS)
- Publesher
Tomsk State University
- Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(32)
- Date:
- DOI
Keywords
граф, планарность, визуализация графа, топологический рисунок графа, алгоритмы на графах, вращение вершин, изометрические циклы, graph, planarity, graph visualization, topological graph drawing, graph algorithms, vertices rotation, isometric cyclesAuthors
References
Курапов С. В., Давидовский М. В. Два подхода к проведению соединений в плоских конструктивах // Компоненты и технологии. 2015. №7. С. 142-147.
Курапов С. В., Давидовский М. В. Топологический подход к проведению соединений в плоских конструктивах // Компоненты и технологии. 2015. №11. С. 127-130.
Апанович З. В. От рисования графов к визуализации информации // Препринт № 148. Новосибирск: ИСИ СО РАН, 2007. 16 c.
Di Battista G., Eades P., Tamassia R., and Tollis I. G. Algorithms for drawing graphs: an annotated bibliography // Comp. Geom. 1994. V.4. No. 5. P. 235-282.
Tamassia R. Handbook of Graph Drawing and Visualization. Boca Raton: Chapman and Hall/CRC, 2013. 844 p.
Курапов С. В., Толок А. В. Методы построения топологического рисунка графа // Автоматика и телемеханика. 2013. №9. C. 78-97.
Kavitha T., Liebchen C., Mehlhorn K., et al. Cycle bases in graphs - characterization, algorithms, complexity, and applications // Comput. Sci. Rev. 2009. No. 3. P. 199-243.
Деза М., Гришухин В. П., Штогрин М. И. Изометрические полиэдральные подграфы в гиперкубах и кубических решетках. М.: МЦНМО, 2007. 192 с.
Рингель Г. Теорема о раскраске карт. М.: Мир, 1977. 126с.
Зыков А. А. Теория конечных графов. Новосибирск: Наука, 1969. 554с.
Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. 455 с.
Харари Ф. Теория графов. М.: Мир, 1973. 300с.
Мак-Лейн С. Комбинаторное условие для плоских графов // Кибернетический сборник. Новая серия. 1970. №7. С. 68-77.
Хопкрофт Дж. Е., ТарьянР.Е. Изоморфизм планарных графов // Кибернетический сборник. Новая серия. 1975. №12. С. 39-61.
Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 480 с.
Раппопорт Л. И., Мороговский Б. Н., Поливцев С. А. Векторная алгебра пересечений // Многопроцессорные вычислительные структуры. 1982. №2(11). С. 53-56.

Planarity testing and constructing the topological drawing of a plane graph (DFS) | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 2(32).
Download full-text version
Counter downloads: 1011