One Sided Crossing Minimization Is NP-Hard for Sparse Graphs

The one sided crossing minimization problem consists of placing the vertices of one part of a bipartite graph on prescribed positions on a straight line and finding the positions of the vertices of the second part on a parallel line and drawing the edges as straight lines such that the number of pairwise edge crossings is minimized. This problem represents the basic building block used for drawing hierarchical graphs aesthetically or producing row-based VLSI layouts. Eades and Wormald [3] showed that the problem is NP-hard for dense graphs. Typical graphs of practical interest are usually very sparse. We prove that the problem remains NP-hard even for forests of 4-stars