S. Hong and H. Nagamochi, "Approximation Algorithms for Crossing Minimisation in Radial Layouts", Algorithmica, Springer, Volume 58, Number 2, pp. 478497, 2010.
We study a crossing minimization problem of drawing a bipartite graph
with a radial drawing of two orbits. Radial drawings are one of wellknown drawing
conventions in social network analysis and visualization, in particular, displaying centrality
indices of actors (Wasserman and Faust, Social Network Analysis: Methods
and Applications. Cambridge University Press, Cambridge, 1994). The main problem
in this paper is called the onesided radial crossing minimization, if the positions of
vertices in the outer orbit are fixed. The problem is known to be NPhard (Bachmaier,
IEEE Trans. Vis. Comput. Graph. 13, 583594, 2007), and a number of heuristics are
available (Bachmaier, IEEE Trans. Vis. Comput. Graph. 13, 583594, 2007). However,
there is no approximation algorithm for the crossing minimization problem in
radial drawings. We present the first polynomial time constantfactor approximation
algorithm for the onesided radial crossing minimization problem.

S. Hong and H. Nagamochi, "New Approximation to the Onesided Radial Crossing Minimisation", Journal of Graph Algorithms and Applications, Vol. 13, no. 2, 179196, 2009.
In this paper, we study a crossing minimization problem in a radial
drawing of a graph. Radial drawings have strong application in social network visualization, for example, displaying centrality indices of actors.
The main problem of this paper is called the onesided radial crossing
minimization between two concentric circles, named orbits, where the positions of vertices in the outer orbit are fixed. The main task of the
problem is to find the vertex ordering of the free orbit and edge routing
between two orbits in order to minimize the number of edge crossings.
The problem is known to be NPhard, and the first polynomial time
15approximation algorithm was presented in.
In this paper, we present a new 3αapproximation algorithm for the
case when the free orbit has no leaf vertex, where α represents the approximation ratio of the onesided crossing minimization problem in a
horizontal drawing. Using the best known result of α =1.4664, our
new algorithm can achieve 4.3992approximation.
