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/2078-7707-2022-3-32-39
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 visu-alized, 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 step-by-step 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. 32-39. doi:10.31114/2078-7707-2022-3-32-39
URL of paper
	http://www.mes-conference.ru/data/year2022/pdf/D035.pdf