Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00182
New Approximation to the Onesided Radial Crossing Minimization
Vol. 13, no. 2, pp. 179196, 2009. Regular paper.
Abstract 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.

Submitted: September 2008.
Reviewed: February 2009.
Revised: March 2009.
Accepted: April 2009.
Final: May 2009.
Published: June 2009.
Communicated by
Giuseppe Liotta
