Computing Radial Drawings on the Minimum Number of Circles - Di Giacomo, Emilio; Didimo, Walter; Liotta, Giuseppe; Meijer, Henk (Journal of Graph Algorithms and Applications, 2005)
A radial drawing is a representation of a graph in which the vertices lie onconcentric circles of finite radius. In this paper we study the problem ofcomputing radial drawings of planar graphs by using the minimum number ofconcentric circles. We assume that the edges are drawn as straight-linesegments and that co-circular vertices can be adjacent. It is proven that theproblem can be solved in polynomial time. The solution is based on acharacterization of those graphs that admit a crossing-free straight-lineradial drawing on k circles. For the graphs in this family, a linear timealgorithm that computes a radial drawing on k circles is also presented. <!---->