Experimental Comparison Between Evolutionary Algorithm and Barycenter Heuristic for the Bipartite Drawing Problem

Abstract

This research investigates the use of intelligent techniques for the bipartite drawing problem (BDP). Due to the combinatorial nature of the solution space, the use of traditional search methods lead to exponential time. Hence, the aim of this paper is to speed up the search time when solving the BDP through the use of Evolutionary Algorithms (EAs) and Barycenter Heuristic (BC). EA is applied on the BDP wherein genetic operators such as crossover and mutation are employed while searching for the best possible solution. The results show that the EA approach guides the search towards optimal solutions and in many instances it outperforms the BC.