GRAPH VISIBILITY REDUCTION METHOD FOR ORTHOGONAL VISUALIZATION OF GRAPH EDGES

Abstract

A Method for Orthogonal Visibility Graph Reduction Using a Graph Neural Network for Orthogonal Edge Routing. The article addresses the current challenge of accelerating orthogonal edge routing, which is an essential component of automatic graph drawing in technical diagrams such as UML diagrams, business process schemas, and electrical circuit designs. Existing state-of-the-art orthogonal edge routing methods rely on constructing a full orthogonal visibility graph followed by an optimal path search, resulting in a quadratic dependency of the number of visibility graph edges on the number of diagram vertices and limiting the feasibility of interactive work with large graphs. An analysis of recent studies and publications has shown that graph neural networks have already been successfully applied to reduce the runtime of graph-based methods in related domains, including search space reduction in combinatorial optimization problems, learning heuristic functions for shortest path search methods, and graph sparsification prior to solving the travelling salesman problem; however, these approaches have not yet been applied to the orthogonal edge routing problem, where the specific geometric structure of the visibility graph and the multi-criteria path cost function require a specialized approach. The goal of this research is to develop a method for orthogonal visibility graph reduction using a graph neural network that would reduce the number of visibility graph edges before performing the optimal path search while maintaining edge routing quality comparable to existing methods. The proposed method consists of four sequential stages: constructing a candidate graph without verifying actual visibility between vertices, classifying edges using a pre-trained graph neural network, pruning edges with a low probability of belonging to the target path, and searching for a path on the reduced graph. The fundamental distinction from existing approaches is that sparsification is performed at the visibility graph construction stage rather than at the path search stage, which allows reducing processing time at both stages. The process of training data generation and neural network training is described, where the output of the existing method is used as a ground truth for recognizing edges that are part of the target paths. A fallback mechanism guarantees that in the case of unsuccessful sparsification, the result of the proposed method is never worse than that of existing methods.