Genetic algorithms for bipartite and outerplanar graph drawings are best
Hongmei He, Mary Newton, Ondřej Sýkora · Loughborough University Institutional Repository (Loughborough University) · 2005
In the circular (other alternate concepts are outerplanar, convex and one-page) drawing one places vertices of a n-vertex m-edge connected graph G along a circle, and the edges are drawn as straight lines.The smallest possible number of crossings in such a drawing of the graph G is called circular (outerplanar,convex, or one-page) crossing number of the graph G.This paper addresses heuristic algorithms to find an ordering of vertices to minimise the number of crossings in the corresponding circular drawing of the graph.New algorithms to find low crossing circular drawings are presented, and compared with algorithm of Mäkinen [4], CIRCULAR+ algorithm of Six and Tollis [5] and algorithm of Baur and Brandes [1].We get better or comparable results to the other algorithms.