Drawing Graphs in Parallel Lines with Artificial Neural Networks

In this work, we propose the use of a multivalued recurrent neural network with the aim of graph drawing. Particularly, the problem of drawing a graph in two parallel lines with the minimum number of crossings between edges is studied, and a formulation for this problem is presented. The neural model MREM is used to solve this problem. This model has been successfully applied to other optimization problems. In this case, a slightly different version is used, in which the neuron state is represented by a two dimensional discrete vector, representing the nodes assigned to a given position in each of the parallel lines. Some experimental simulations have been carried out in order to compare the efficiency of the neural network with a heuristic approach designed to solve the problem at hand. These simulations confirm that our neural model outperforms the heuristic approach, obtaining a lower number of crossings on average.