ISSN 2079-3537      

 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                                                                                             

Scientific Visualization, 2020, volume 12, number 1, pages 90 - 102, DOI: 10.26583/sv.12.1.08

Generating a topological drawing of the flat part of a nonplanar graph

Authors: S.V.  Kurapov1,A, M.V. Davidovsky2,B, A.V. Tolok3,C

A Zaporozhye National University, 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 consider the issues of applying the diakoptic approach to constructing a topological drawing of the planar part of a non-planar graph. It is demonstrated that the first stage of constructing a topological drawing is based on the matroid properties of the set of graph isometric cycles. In the article, we propose a method for constructing a topological drawing of the planar part of a non-planar graph using the methods of structure numbers algebra. The initial solution is based on the set of graph isometric cycles that allows application of discrete optimization methods. The second stage of joining the cycles is based on the methods of vector algebra of intersections. In the article we describe the essential mathematical concepts and structures for solving the problem of constructing a planar topological drawing of a non-planar graph. The presentation is supported by detailed illustrative examples.

 

Keywords: graph, rotation of graph vertices, isometric cycles, planarity, planar part of a graph.