Genetic algorithms for drawing bipartite graphs
Erkki Mäkinen, Mika Sieranta · International Journal of Computer Mathematics · 1994
This paper introduces genetic algorithms for the level permutation problem (LPP). The problem is to minimize the number of edge crossings in a bipartite graph when the order of vertices in one of the two vertex subsets is fixed. We show that genetic algorithms outperform the previously known heuristics especially when applied to low density graphs. Values for various parameters of genetic LPP algorithms are tested.