×

zbMATH — the first resource for mathematics

Minimizing crossings in hierarchical digraphs with a hybridized genetic algorithm. (English) Zbl 1122.68087
Summary: Producing clear and intelligible layouts of hierarchical digraphs knows a renewed interest in information visualization. Recent experimental results show that metaheuristics are well-adapted methods for this problem. In this paper, we develop a new Hybridized Genetic Algorithm for arc crossing minimization. It follows the basic scheme of a GA with two major differences: problem-based crossovers adapted from ordering GAs are combined with a local search strategy based on averaging heuristics. Computational testing was performed on a set of 180 random hierarchical digraphs of standard sizes with various structures. Results show that the Hybridized Genetic Algorithm significantly outperforms Tabu Search-which is one of the best known methods for this problem- and also a multi-start descent except for highly connected graphs.
MSC:
68R10 Graph theory (including graph drawing) in computer science
90C59 Approximation methods and heuristics in mathematical programming
Software:
GVF
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andrews, K. (1995). ”Visualizing Cyberspace: Information Visualization in the Harmony Internet Browser.” In: Proc. IEEE Symp. Inform. Visual, IEEE Press, pp. 97–105.
[2] Bridgeman, S. and R. Tamassia. (2002). ”A User Study in Similarity Measures for Graph Drawing.” J. of Graph Algorithms and Applications 6(3), 225–254. · Zbl 1027.68098
[3] Buntine, W. (1996). ”Graphical Models for Knowledge Discovery.” In: U. Fayyad, G. Piatetsky- Shapiro, P. Smyth, and R. S. Uthurasamy (eds.), Advances in Knowledge Discovery and Data Mining, MIT Press, pp. 59–83.
[4] Coello Coello, C.A., D.A. Van Veldhuizen, and G. B. Lament. (2002). Evolutionary Algorithms for Solving Multi-Objective Problems, Vol. 5 of Genetic Algorithms and Evolutionary Computation.Kluwer Academic Publishers. ISBN 0-3064–6762-3. · Zbl 1130.90002
[5] Carpano, M. (1980). ”Automatic Display of Hierarchized Graphs for Computer Aided Decision Analysis.” IEEE Trans. Syst., Man, Cybern. 10(11), 705–715. · doi:10.1109/TSMC.1980.4308390
[6] Di-Battista, G., P. Eades, R. Tamassia, and I. Tollis. (1999). Graph Drawing–Algorithms for the Visualization of Graphs. Prentice Hall. · Zbl 1057.68653
[7] Eades, P., W. Lai, K. Misue, and K. Sugiyama. (1991). ”Preserving the Mental Map of A Diagram.” In Proc. of Compugraphics, pp. 24–33.
[8] Eades, P. and N. Wormald. (1994). ”Edge Crossings in Drawings of Bipartite Graphs.” Algorith- mica 11, 379–403. · Zbl 0804.68107 · doi:10.1007/BF01187020
[9] Eschbach, T., W. Gtinther, R. Drechsler, and B. Becker. (2002). ”Crossing Reduction by Windows Optimization.” In: Proc. of the 10th Int. Symposium on Graph Drawing, LNCS 2528, Springer Verlag, pp. 285–294. · Zbl 1037.68583
[10] Gansner, E., S. North, and K. Vo. (1988). ”A Program that Draws Directed Graphs.” Software Practice and Experience 18(11), 1047–1062. · Zbl 0661.68067 · doi:10.1002/spe.4380181104
[11] Garey, M. and D. Johnson. (1983). ”Crossing Number is NP-complete.” J. Algebraic Discrete Methods 4(3), 312–316. · Zbl 0536.05016 · doi:10.1137/0604033
[12] Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley. · Zbl 0721.68056
[13] Groves, L.J., Z. Michalewicz, P.V. Elia, and C.Z. Janikow. (1990). ”Genetic Algorithms for Drawing Directed Graphs.” In: Proc. of the 5th Int. Symp. on Methodologies for Intelligent Systems, Elsevier, pp. 268–276.
[14] Herman, I., G. Melangon, and S. Marshall. (2000). ”Graph Visualization and Navigation in Information Visualization: A Survey.” IEEE Trans. Visual. Comput. Graphics 6(1), 24–43. · Zbl 05108063 · doi:10.1109/2945.841119
[15] Kargupta, H., K. Deb, and D. Goldberg. (1992). ”Ordering Genetic Algorithms and Deception.” In: Proc. Parallel Problem Solving from Nature, Elsevier Sc, Vol. 2, pp. 47–56.
[16] Kraak, M.J. and A. Brown. (2000). Web Cartography: Developments and Prospects. Taylor & Francis. ISBN 0748408681.
[17] Kuntz, P., B. Pinaud, and R. Lehn. (2004). ”Elements for the Description of Fitness Landscapes Associated with Local Operators for Layered Drawings of Directed Graphs.” In: M. Resende and J. de Sousa (eds.), Metaheuristics: Computer Decision-Making Vol. 86 of Applied Optimization. Kluwer Academic Publishers, pp. 405\^4–20.
[18] Laguna, M., R. Marti, and V. Vails. (1997). ”Arc Crossing Minimization in Hierarchical Digraphs with Tabu Search.” Computers and Operation Research 24(12), 1175–1186. · Zbl 0883.90119 · doi:10.1016/S0305-0548(96)00083-4
[19] Mäkinen, E. and M. Sieranta. (1994). ”Genetic Algorithms for Drawing Bipartite Graphs.” Int. J. of Computer Mathematics 53(3-4), 157–166. · Zbl 0839.68072 · doi:10.1080/00207169408804322
[20] Marti, R. (2001). ”Arc Crossing Minimization in Graphs with GRASP.” HE Trans 33(10), 913–919.
[21] Matuszewski, C., R. Schonfeld, and P. Molitor. (1999). ”Using Sifting for K-layer Straightline Crossing Minimization.” In Proc. of the 7th Int. Symposium on Graph Drawing, LNCS 1731, Springer Verlag, pp. 217–224.
[22] Mutzel, P. and M. lunger. (2003). Graph Drawing Software. Springer Verlag. ISBN: 3-540–00881-0. · Zbl 1029.68145
[23] North, S. (1996). ”Incremental Layout in Dynadag.” In Proc. of Graph Drawing’95 Vol. 1027 of Lecture Notes in Computer Science, Springer-Verlag, pp. 409–418.
[24] Ochoa-Rodriguez, A. and A. Rosete-Suàrez. (1995). ”Automatic Graph Drawing by Genetic Search.” In Proc. of the 11th Int. Conf. on CAD, CAM, Robotics and Manufactories of the Future, pp. 982–987.
[25] Papakostas, A., J. Six, and I. Tollis. (1997). ”Experimental and Theoretical Results in Interactive Orthogonal Graph Drawing.” In Proc. of Graph Drawing’96, Vol. 1190 of Lecture Notes in Computer Sciences, Springer Verlag, pp. 371–386.
[26] Purchase, H. (2000). ”Effective Information Visualisation: A Study of Graph Drawing Aesthetics and Algorithms.” Interacting with Computers 13(2).
[27] Rowe, L., M. Davis, E. Messinger, C. Meyer, C. Spirakis, and A. Tuan. (1987). ”A Browser for Directed Graphs.” Software - Practice and Experience 17(1), 61–76. · doi:10.1002/spe.4380170107
[28] Sugiyama, K., S. Tagawa, and M. Toda. (1981). ”Methods for Visual Understanding of Hierarchical Systems.” IEEE Trans. Syst., Man, Cybern 11(2), 109–125. · doi:10.1109/TSMC.1981.4308636
[29] Tettamanzi, A.G. (1998). ”Drawing Graphs with Evolutionary Algorithms.” In Proc. of Conf. on Adaptive Computing in Design and Manufacture, ACDM, pp. 325–338.
[30] Utech, J., J. Branke, H. Schmeck, and P. Eades. (1998). ”An Evolutionary Algorithm for Drawing Directed Graphs.” In: Proc. of the Int. Conf. on Imaging Science, Systems and Technology, CSREA Press, pp. 154–160.
[31] Warfield, J. (1977). ”Crossing Theory and Hierarchy Mapping.” IEEE Trans. Syst., Man, Cybern 7(7), 505–523. · Zbl 0367.93004
[32] Whitley, D. and N. Yoo. (1995). ”Modeling Simple Genetic Algorithms for Permutation Problems.” In: L. D. Whitley and M. D. Vose (eds.): Fundations of Genetic Algorithms III pp. 163–184, Morgan Kaufmann.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.