## New circular drawing algorithms

online resource

posted on 25.09.2006, 15:35 by Hongmei He, Ondrej SykoraIn 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.

### History

#### School

- Science

#### Department

- Computer Science