Logo

Login | Create Account

Two New Heuristics for Two-Sided Bipartite Graph Drawing

Newton, Matthew and Sykora, Ondrej and Vrt'o, Imrich (2002) Two New Heuristics for Two-Sided Bipartite Graph Drawing. [Conference Paper]

Full text not available from this repository.

Abstract

Two new heuristic strategies are studied based on heuristics for the linear arrangement problem and a stochastic hill-climbing method for the two-sided bipartite crossing number problem. These are compared to the standard heuristic for two-sided bipartite drawing based on iteration of the barycentre method. Our experiments show that they can efficiently find good solutions.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.420 Crossings
ID Code:208
Deposited By:Martinez Leon, Victoria
Deposited On:07 Dec 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2528&spage=312

Repository Staff Only: item control page

References

1. Bastert, O., Matuszewski, C.: Layered drawings of digraphs. In: Drawing Graphs, Methods and Models (eds. Kaufmann, M. Wagner D.), LNCS 2025, Spinger (2001) 87-118

2. Boisvert, R., Pozo, R., Remington, K., Barett, R., Dongarra, J.: Matrix Market: a web resource for test matrix collections. In: The Quality of Numerical Software: Assessment and Enhancement (ed. Boisvert, R.), Chapman and Hall, London, (1997) 125-137, Matrix Market is available at the URL: http:.//math.nist.gov/MatrixMarket/

3. Dresbach, S.: A new heuristic layout algorithm for DAGs. In: Operations Research Proceedings 1994 (eds. Derigs, U., Drexl, A.B.A.), Springer (1994) 121-126.

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

5. Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for Visualization of graphs. Prentice Hall (1999).

6. Eades, P., Kelly, D.: Heuristics for reducing crossings in 2-layered networks. Ars Combin. 21 (1986) 89-98

7. Eades, P., Wormland, N.: Edge crossings in drawings of bipartite graphs. Algorithmica 11 (1994) 379-403

8. Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebraic Disc. Meth. 4 (1983) 312-316

9. Juvan, M., Mohar, B.: Optimal linear labellings and eigenvalues of graphs. Discrete Appl. Math. 36 (1992) 153-168

10. Jünger, M., Mutzel, P.: 2-Layer straight line crossing minimization: Performance of exact and heuristic algorithms. J. Graph Algorithms Appl., 1 (1997) 1-25

11. Knuth, D.E.: The Stanford GraphBase: A platform for combinatorial computing. Addision-Wesley, (1993)

12. Koren, Y., Harel, D.: A multi-scale algorithm for the linear arrangement problem. In: 28th Intl. Workshop on Graph-Theoretic Concepts in Computer Science (WG'2002), LNCS, Springer (2002), to appear

13. Matuszewski, C., Schönfeld, R., Molitor, P.: Using stifting for k-layer straightline crossing minimization. In: 7th Intl. Symp. on Graph Drawing (GD '99), LNCS 1731, Springer (1999) 217-224

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

15. Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical Recipes in C. The Art of Scientific Computing. Second edition, Cambridge University Press (1992) http://www.nr.com

16. Purchase, H.: Which aesthetic has the greatest effect on human understanding? In: 5th Intl. Symp. on Graph Drawing (GD '97), LNCS 1353, Springer (1998) 248-261

17. Sarrafzadeh, M., Wong, C.K.: An Introduction to VLSI Physical Design. McGraw Hill, (1996)

18. Shahrokhi, F., Sykora, O., Székely, L.A., Vrt'o, I.: On bipartite drawings and the linear arrangement problem. SIAM J. Computing 30 (2001), 1773-1789

19. Shahrokhi, F., Sykora, O., Székely, L.A., Vrt'o, I.: A new lower bound for the bipartite crossing number with algorithmic applications. Theoretical Computer Science 245 (2000) 281-294

20. Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics SMC-11 (1981) 109-125

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.