An Improved Bound on the One-Sided Minimum Crossing Number in Two-Layered Drawings

Given a bipartite graph G = (V,W,E), a two-layered drawing consists of placing nodes in the first node set V on a straight line L₁ and placing nodes in the second node set W on a parallel line L₂. The one-sided crossing minimization problem asks one to find an ordering of nodes in V to be placed on L₁ so that the number of arc crossings is minimized. In this paper we use a 1.4664-approximation algorithm for this problem. This improves the previously best bound 3 due to P. Eades and N. C. Wormald Edge crossing in drawing bipartite graphs, Algorithmica 11 (1994), 379-403].