One Sided Crossing Minimization Is NPHard for Sparse GraphsMunoz, Xavier and Unger, W. and Vrt'o, Imrich (2002) One Sided Crossing Minimization Is NPHard for Sparse Graphs. In: Graph Drawing 9th International Symposium, GD 2001, September 2326, 2001 , pp. 115123(Official URL: http://dx.doi.org/10.1007/3540458484_10). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540458484_10
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 rowbased VLSI layouts. Eades and Wormald [3] showed that the problem is NPhard for dense graphs. Typical graphs of practical interest are usually very sparse. We prove that the problem remains NPhard even for forests of 4stars.
Actions (login required)
