New circular drawing algorithms

2006-09-25T15:35:17Z (GMT) by Hongmei He Ondrej Sykora
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 Makinen, CIRCULAR+ algorithm of Six and Tollis and algorithm of Baur and Brandes. We get better or comparable results to the other algorithms.