New circular drawing algorithms
Hongmei He
Ondrej Sykora
2134/2386
https://repository.lboro.ac.uk/articles/New_circular_drawing_algorithms/9403790
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.
2006-09-25 15:35:17
untagged