Logo

Login | Create Account

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. [Conference Paper]

Full text not available from this repository.

Abstract

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
Classifications:G Algorithms and Complexity > G.420 Crossings
ID Code:506
Deposited By:Arnopolina, Galina
Deposited On:21 Dec 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2265&spage=115

Repository Staff Only: item control page

References

1. C. Demetrescu, I. Finocchi. Removing cycles for minimizing crossings. J. Experimental Algorithmics. to appear.

2. G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph drawing: algorithms for the visualization of graphs. Prentice Hall, New Jersey, 1999.

3. Eades, P. and N.C. Wormald. Edge crossings in drawings of bipartite graphs. Algorithmica 10 (1994)379-403.

4. Eades, P. and S. Whitesides. Drawing graphs in two layers. Theoretical computer science 131 (1994) 361-374.

5. M.R. Garey and D.S. Johnson. Crossing number is np-complete, SIAM J. Algebraic and Discrete Methods 4(1983), 312-316.

6. F. Gavril. Some NP-complete problems on graphs. In: 11th Conf. on Information Sciences and Systems. John Hopkins University Press, Baltimore (1977) 91-95.

7. M. Jünger and P. Mutzel. 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. J. Graph Algorithms 1 (1999), 11-25.

8. C. Matuszewski, R. Schonfeld, and P. Molitor. Using sifting for k-layer crossing minimization. In Jan Kratochvíl, editor, Graph Drawing '99, volume 1971 of Lecture Notes in Computer Science, pages 217-224. Springer-Verlag.

9. P. Mutzel. Optimization in leveled graphs. In: Pardalos, M., Floudas, C.A. (eds.), Encyclopedia of Optimization, Kluwer, Dordrecht (2001).

10. H. Purchase. Which aesthetichas the greatest effect on human understanding? In G. Di Battista, ed., Proc. of the Symp. on Graph Drawing, GD'97, vol. 1353 of LNCS, pages 248-261. Springer Verlag, 1997.

11. C. Sechen. VLSI placement and global routing using simulated annealing. Kluwer, Dordrecht (1988).

12. Shahrokhi, F., Sýkora, O., Székely, L. A., Vrt'o, I. On bipartite drawings and the linear arrangement problem. SIAM J. Comp. 30 (2000) 1773-1789.

13. M. Stallmann, F. Brglez, D. Ghosh. Heuristics, experimental subjects, and treatment evaluation in bigraph crossing minimization. J. Experimental Algorithmics, to appear.

14. R.H. Stanley. Enumerative combinatorics. Wadsworth & Brooks, Monterey (1986).

15. K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical systems. IEEE Trans. Syst. Man. Cybern., SMC-11(2):109-125, 1981.

16. A. Yamaguchi, A. Sugimoto. An Approximation Algorithm for the two-layered graph drawing problem. In: 5th Annual Intl. Conf. on Comp. and Comb. LNCS, vol. 1627. Springer-Verlag, Berlin (1999) 81-91.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.