An Improved Approximation to the One-Sided Bilayer Drawing

Given a bipartite graph G=(V,W,E), a bilayer drawing consists of placing nodes in the first vertex set V on a straight line L₁ and placing nodes in the second vertex set W on a parallel line L₂. The one-sided crossing minimization problem asks 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 prove that there always exits a solution whose crossing number is at most 1.4664 times of a well-known lower bound that is obtained by summing up {c _uv , c _vu } over all node pairs u,vεV, where c _uv denotes the number of crossings generated by arcs incident to u and v when u precedes v in an ordering.