Two New Heuristics for Two-Sided Bipartite Graph Drawing

Newton, Matthew and Sýkora, Ondrej and Vrt'o, Imrich (2002) Two New Heuristics for Two-Sided Bipartite Graph Drawing. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 312-319 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_29).

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
Additional Information:10.1007/3-540-36151-0_29
Classifications:G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.420 Crossings
ID Code:208

Repository Staff Only: item control page

References

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

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/

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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