## One Sided Crossing Minimization Is NP-Hard for Sparse Graphs
Munoz, Xavier and Unger, W. and Vrt'o, Imrich
(2002)
Full text not available from this repository. ## AbstractThe 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.
Repository Staff Only: item control page References |