One Sided Crossing Minimization Is NP-Hard for Sparse Graphs

Munoz, Xavier and Unger, W. and Vrt'o, Imrich (2002) One Sided Crossing Minimization Is NP-Hard for Sparse Graphs. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001 , pp. 115-123(Official URL:

Full text not available from this repository.


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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-45848-4_10
Classifications: G Algorithms and Complexity > G.420 Crossings

Actions (login required)

View Item View Item