Home
Authors Papers Year of conference Themes Organizations To MES conference
Topological Graph Drawings 




Authors 
 Kurapov S.V. 
 Davidovsky M.V. 
Date of publication 
 2022 
DOI 
 10.31114/20787707202233239 

Abstract 
 Graph theory provides models and methods for analyzing structures of an arbitrary nature, where a graph can be viewed as a form of structure modeling. In the process of solving applied problems, such structures need to be visualized, transformed, stored and displayed. The best form of graph visualization is its drawing. Graph drawing (visualization) methods are widely used in such fields as biological sciences, artificial intelligence, financial information analysis, designing flat constructs, where the connections between elements are located in several parallel planes – integrated circuits, printed circuit boards, etc. However, modern methods of graph theory represent objects up to isomorphism without distinguishing between their images (graph drawings). Moreover, it is desirable that the drawing can be stored and processed using topological methods, without making geometric constructions in the process of transformations. The paper considers a general stepbystep approach to solving the problems of constructing a topological drawing of various types of graphs – the main stages of constructing a topological drawing of a graph are considered, the main definitions and limitations of the proposed mathematical models are introduced. The models are based on discrete optimization methods and the theory of graph vertex rotation. To build a mathematical model, the problem of selecting a flat part of a graph is solved, which is considered as a combinatorial problem of finding a subset of isometric cycles of a graph. The presented method for extracting the flat part of the graph is based on extracting the basis of isometric cycles of the graph by using the modified Gaussian algorithm, followed by extracting the flat part by the gradient descent method. The presented mathematical models and methods make it possible to effectively build a geometric prototype of a topological graph drawing, which is demonstrated by specific examples. 
Keywords 
 graph, topological graph drawing, vertex rotation diagram, isometric cycles. 
Library reference 
 Kurapov S.V., Davidovsky M.V. Topological Graph Drawings // Problems of Perspective Micro and Nanoelectronic Systems Development  2022. Issue 3. P. 3239. doi:10.31114/20787707202233239 
URL of paper 
 http://www.mesconference.ru/data/year2022/pdf/D035.pdf 

