Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00114
Computing Radial Drawings on the Minimum Number of Circles
Vol. 9, no. 3, pp. 365389, 2005. Regular paper.
Abstract A radial drawing is a representation of a graph in which the vertices lie on
concentric circles of finite radius. In this paper we study the problem of
computing radial drawings of planar graphs by using the minimum number of
concentric circles. We assume that the edges are drawn as straightline
segments and that cocircular vertices can be adjacent. It is proven that the
problem can be solved in polynomial time. The solution is based on a
characterization of those graphs that admit a crossingfree straightline
radial drawing on k circles. For the graphs in this family, a linear time
algorithm that computes a radial drawing on k circles is also presented.
