MODIFICATION OF THE THREAD METHOD WITH USING THE GAMMA ALGORITHMFOR GRAPH TOPOLOGICAL DRAWING BUILDING

Abstract

In this paper, one consider a modified algorithm of the thread method, which is designed to check a graph for planarity with the simultaneous building a topological drawing of a planar graph in the form of a system of isometric cycles and lists of rotation of graph vertices. Obtaining the rotation of the graph vertices immediately solves two important problems: the problem of checking the graph for planarity and the problem of building a topological drawing of a planar graph. The system of graph isometric cycles obtained as a result of the algorithm induces the rotation of vertices to describe the topological pattern of a planar graph for the purposes of subsequent visualization. The topological drawing of the flat part of the graph makes it possible to describe the process of planarization by algebraic methods without making any geometric constructions on the plane. The presented algorithm is based on the rearrangement of the reference cycle and the construction of a list of reverse routes. The basis of the calculation is the construction of a matrix of fundamental cycles based on the construction of the spanning tree of the graph by the depth-first search method. Based on the matrix of fundamental cycles, the chains that form the routes are selected. To obtain a system of isometric cycles, routes are embedded using a modified gamma algorithm. An adapted version of the gamma algorithm in the application of the thread method makes it possible to embed path-forming chains into graph cycles and simplifies the task of finding suitable cycles for this. Adaptation of the gamma algorithm includes an additional predictive index to determine the possibility of embedding subsequent paths in a given cycle. Graph planarization is the most important subtask in solving many relevant applied problems, such as designing complex products and systems, flat constructs, analyzing social networks, etc.