Genetic algorithms for bipartite and outerplanar graph drawings are best!
2006-09-27T16:15:03Z (GMT) by
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), 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  and  on more important suites of graphs and get better results.