On the one-sided crossing minimization in a bipartite graph with large degrees (Q1770400)

Given a bipartite graph \(G=(V,W,E)\), a 2-layered drawing consists of placing nodes in the first node set \(V\) on a straight line \(L_1\) and placing nodes in the second node set \(W\) on a parallel line \(L_2\). For a given ordering of nodes in \(W\) on \(L_2\), the one-sided crossing minimization problem asks to find an ordering of nodes in \(V\) on \(L_1\) so that the number of arc crossings is minimized. A well-known lower bound \(LB\) on the minimum number of crossings is obtained by summing up \(\min c_{uv},c_{vu}\) over all node pairs \((u,v)\in V\), where \(c_{uv}\) denotes the number of crossings generated by arcs incident to \(u\) and \(v\) when \(u\) precedes \(v\) in an ordering. In this paper, we prove that there always exists a solution whose crossing number is at most \((1.2964+12/(\delta -4))LB\) if the minimum degree \(\delta\) of a node in \(V\) is at least 5.