Scientific Visualization, 2018, volume 10, number 4, pages 53 - 74, DOI: 10.26583/sv.10.4.05
A modified algorithm for planarity testing and constructing the topological drawing of a graph. The thread method.
Authors: S.V. Kurapov1,A, M.V. Davidovsky2,B, A.V. Tolok3,C
A Zaporizhzhia National Universite, Ukraine
B Zaporozhye Institute of Postgraduate Pedagogical Education, Ukraine
C Moscow State Technological University «STANKIN», Russia
1 ORCID: 0000-0003-4563-7227, lilili5050@rambler.ru
2 ORCID: 0000-0002-9472-3351, m.davidovsky@gmail.com
3 ORCID: 0000-0002-7257-9029, a.tolok@stankin.ru
Abstract
In this article we present a modified algorithm for graph planarity testing with simultaneous con-struction of a mathematical framework for representing the topological drawing of a plane graph. This mathematical framework is based on the notions of graph isometric cycles and rotation of graph vertices. Obtaining the rotation of graph vertices solve two major problems: the problem of graph planarity testing and the problem of constructing the topological drawing of a planar graph. The system of graph isometric cycles, which is obtained as a result of the algorithm execution, induces the rotation of graph vertices for representing the topological drawing of the graph. The topological drawing is used subsequently for visualization of the plane graph. The topological drawing of the flat part of a graph allows describing the process of planarization by algebraic methods without making any geometric constructions on the plane. The proposed algorithm is based on the reconstruction of the reference cycle and construction of reverse path blocks. The basis for calculation is the selection of the DFS-tree of the graph by the depth-first-search meth-od. Visualization of planar graphs is one of the most important sub-tasks in addressing a number of topical applications, such as the design of complex products and systems, flat constructions, social network analysis and many others. The computational complexity of the algorithm is esti-mated as O(m) = f1(m) + f2(m), where m – is the number of graph edges.
Keywords: graph, planarity testing, graph visualization, topological graph drawing, vertices rotation diagram, isometric cycles, reference cycle.
