The problem of pseudo-optimal placement of a graph on a plane

Abstract

The paper is devoted to the problem of placing a graph. Graphs provide an opportunity to present information in a visual and easy to understand form, so the problem of developing various algorithms for automatic placement of graphs on the plane is very relevant. In this paper, we propose a generalized mathematical model of the problem that allows us to consider the placement problem in n-dimensional space as the problem of finding a permutation of n elements. Based on the mathematical description “Hebene”, an heuristic algorithm is built. Computational experiments were carried out on all pairwise nonisomorphic connected graphs up to and including 9. The algorithm found the optimal solution in more than 50% of cases, and in other situations the algorithm also produced acceptable solutions.