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.