Genetic algorithms for bipartite and outerplanar graph drawings are best!

We design genetic algorithms with small populations for two basic problems of graph drawing: the one-sided bipartite drawing and the outerplanar drawing. We compare our results for the one-sided bipartite drawing problem with Penalty Minimisation (PM)[3], the best one-sided heuristic currently available. For graphs without a structural symmetry, our genetic algorithm achieves drawings with lower numbers of crossings than PM. If run on different initial random seeds and for a longer time, we can achieve same results as PM for graphs with a symmetrical structure. We compare performance of our genetic algorithm for the outerplanar drawing with the previously known best heuristic algorithms such as [2] and [7] on more important suites of graphs and get better results.