HeSyk04.pdf (232.21 kB)
0/0

New circular drawing algorithms

Download (232.21 kB)
online resource
posted on 25.09.2006 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.

History

School

  • Science

Department

  • Computer Science

Pages

215163 bytes

Citation

HE and SÝKORA, 2004. New circular drawing algorithms. IN: Proceedings of the Workshop on Information Technologies - Applications and Theory (ITAT), Slovakia, September 15-19

Publication date

2004

Notes

This is a conference paper

Language

en

Exports

Logo branding

Keyword(s)

Exports