S. Hong and H. Nagamochi, "Approximation Algorithms for Crossing Minimisation in Radial Layouts", Algorithmica, Springer, Volume 58, Number 2, pp. 478-497, 2010.

We study a crossing minimization problem of drawing a bipartite graph with a radial drawing of two orbits. Radial drawings are one of well-known 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 one-sided radial crossing minimization, if the positions of vertices in the outer orbit are fixed. The problem is known to be NP-hard (Bachmaier, IEEE Trans. Vis. Comput. Graph. 13, 583-594, 2007), and a number of heuristics are available (Bachmaier, IEEE Trans. Vis. Comput. Graph. 13, 583-594, 2007). However, there is no approximation algorithm for the crossing minimization problem in radial drawings. We present the first polynomial time constant-factor approximation algorithm for the one-sided radial crossing minimization problem.

S. Hong and H. Nagamochi, "New Approximation to the One-sided Radial Crossing Minimisation", Journal of Graph Algorithms and Applications, Vol. 13, no. 2, 179-196, 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 one-sided 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 NP-hard, and the first polynomial time 15-approximation 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 one-sided crossing minimization problem in a horizontal drawing. Using the best known result of α =1.4664, our new algorithm can achieve 4.3992-approximation.

C. Bachmaier, H. Buchner, M. Forster and S. Hong, "Crossing minimization in Extended Level Drawings of Graphs", Discrete Applied Mathematics, 158(3), pp. 159-179, 2010, Elsevier.

The most popular method of drawing directed graphs is to place vertices on a set of horizontal or concentric levels, known as level drawings. Level drawings are well studied in Graph Drawing due to their strong application for the visualization of hierarchy in graphs. There are two drawing conventions: Horizontal drawings use a set of parallel lines and radial drawings use a set of concentric circles.
In level drawings, edges are only allowed between vertices on different levels. However, many real world graphs exhibit hierarchies with edges between vertices on the same level. In this paper, we initiate the new problem of extended level drawings of graphs, which was addressed as one of the open problems in social network visualization, in particular, displaying centrality values of actors. More specifically, we study minimizing the number of edge crossings in extended level drawings of graphs. The main problem can be formulated as the extended one-sided crossing minimization problem between two adjacent levels, as it is folklore with the one-sided crossing minimization problem in horizontal drawings.
We first show that the extended one-sided crossing minimization problem is NP-hard for both horizontal and radial drawings, and then present efficient heuristics for minimizing edge crossings in extended level drawings. Our extensive experimental results show that our new methods reduce up to 30% of edge crossings.

Christoph Buchheim, Seok-Hee Hong: Crossing Minimization for Symmetries. Theory Comput. Syst. 38(3): 293-311 (2005)

We consider the problem of drawing a graph with a given symmetry such that the number of edge crossings is minimal. We show that this problem is NP-hard, even if the order of orbits around the rotation center or along the reflection axis is fixed.We devise an O(m logm) algorithm for computing a crossing minimal drawing if inter-orbit edgesmaynot cross orbits, showing in particular that intra-orbit edges do not contribute to the NP-hardness of the crossing minimization problem for symmetries.