Visualization of Graphs with a Minimum Number of Intersections of Edges Using a Hierarchical Approach

Currently, interest in image graphs is associated with the growing need for information visualization. This paper focuses on hierarchical graphs, where vertices are located on vertical layers, and the edges connecting pairs of vertices are represented by oriented line segments that go in the same direction. Optimization of aesthetics is aimed at improving the readability and memorization of information contained in the graph. Crossing ribs is by far the most important aesthetic criterion. In this paper, we studied methods for solving the problem of minimizing the number of intersections of edges during graph visualization using a hierarchical approach. The practical basis of the study became the main part for analyzing the dependence of the choice of the initial (root) vertex of the graph on the number of intersections of edges. To solve this problem, the Sugiyama method was chosen. This method is implemented and tested on various graphs, as well as computational experiments.