Abstract
Automated graph-drawing systems utilize procedures to place vertices and arcs in order to produce graphs with desired properties. Incremental or dynamic procedures are those that preserve key characteristics when updating an existing drawing. These methods are particularly useful in areas such as planning and logistics, where updates are frequent. We propose a procedure based on the scatter search methodology that is adapted to the incremental drawing problem in hierarchical graphs. These drawings can be used to represent any acyclic graph. Comprehensive computational experiments are used to test the efficiency and effectiveness of the proposed procedure.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
See http://www.infovis-wiki.net for resources on visual analytics.
References
Böhringer, K.F., Paulisch, F.N.: Using constraints to achieve stability in automatic graph layout algorithms. In: Proceedings of CHI’90, pp. 43–51. ACM (1990)
Branke, J.: Dynamic graph drawing. In: Wagner, D., Kaufmann, M. (eds.) Drawing Graphs: Methods and Models, pp. 228–246. Springer, Berlin (2001)
Carpano, M.: Automatic display of hierarchized graphs for computer-aided decision analysis. IEEE Trans. Syst. Man Cybern. 10(11), 705–715 (1980)
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.: Graph Drawing: Algorithms for the Visualization of Graphs, 1st edn. Prentice Hall PTR, Upper Saddle River (1998)
Duarte, A., Pantrigo, J.J., Pardo, E.G., Sánchez-Oro, J.: Parallel variable neighbourhood search strategies for the cutwidth minimization problem. IMA J. Manag. Math. 27(1), 55–73 (2016)
Feo, T.A., Resende, M.G.: Greedy randomized adaptive search procedures. J. Glob. Optim. 6(2), 109–133 (1995)
Garey, M., Johnson, D.: Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods 4(3), 312–316 (1983)
Glover, F.: Tabu search and adaptive memory programming—advances, applications and challenges. In: Barr, R.S., Helgason, R.V., Kennington, J.L. (eds.) Interfaces in Computer Science and Operations Research: Advances in Metaheuristics, Optimization, and Stochastic Modeling Technologies, pp. 1–75. Springer, Boston (1997)
Glover, F., Laguna, M.: Tabu Search. Kluwer Academic Publishers, Norwell (1997)
Hansen, P., Mladenović, N., Moreno-Pérez, J.: Variable neighborhood search: methods and applications. 4OR 6(4), 319–360 (2008)
Kaufmann, M., Wagner, D.: Drawing Graphs: Methods and Models. Lecture Notes in Computer Science. Springer, Berlin (2001)
Laguna, M., Martí, R.: GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS J. Comput. 11, 44–52 (1999)
Laguna, M., Martí, R.: Scatter Search: Methodology and Implementations in C. Kluwer Academic Publisher, Norwell (2003)
Laguna, M., Marti, R., Valls, V.: Arc crossing minimization in hierarchical digraphs with tabu search. Comput. Oper. Res. 24(12), 1175–1186 (1997)
Martí, R., Estruch, V.: Incremental bipartite drawing problem. Comput. Oper. Res. 28(13), 1287–1298 (2001)
Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997)
Mutzel, P., Jünger, M., Leipert, S.: How to layer a directed acyclic graph. In: Graph Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 23–26, 2001 Revised Papers, pp. 16–30. Springer, Berlin (2002)
North, S.C.: Incremental layout in DynaDAG. In: Proceedings of of Graph Drawing’95, volume 1027 of Lecture Notes in Computer Science, pp. 409–418. Springer, Berlin (1996)
Pinaud, B., Kuntz, P., Lehn, R.: Dynamic graph drawing with a hybridized genetic algorithm. In: Parmee, I.C. (ed.) Adaptive Computing in Design and Manufacture VI, 2004, pp. 365–375. Springer, Bristol (2004)
Purchase, H.: Which aesthetic has the greatest effect on human understanding? In: Proceedings of Graph Drawing’97, vol 1353 de Lecture Notes in Computer Science, pp. 248–261. Springer, Berlin (1997)
Purchase, H.: Effective information visualization: a study of graph drawing aesthetics and algorithms. Interact. Comput. 13(2), 147–162 (2000)
Resende, M.G., Ribeiro, C.C.: GRASP with path-relinking: recent advances and applications. In: Ibaraki, T., Nonobe, K., Yagiura, M. (eds.) Metaheuristics: Progress as Real Problem Solvers, pp. 29–63. Springer, New York (2005)
Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybern. (SMC) 11(2), 109–125 (1981)
Acknowledgements
This work has been partially supported by the Spanish “Ministerio de Economía y Competitividad” and by “Comunidad de Madrid,” Grants Refs. TIN2015-65460-C02 and S2013/ICE-2894, respectively. Additionally, Prof. Martinez-Gavara and Sánchez-Oro thank “Programa de Ayudas para Estancias Cortas en otras Universidades y Centros de Investigación,” Universidad de Valencia (Ref. UV-INV_EPDI16-384465) and “Ayudas a la Movilidad Predoctoral para Estancias Breves,” Ministerio de Economía y Competitividad (Ref. EEBB-I-16-11312) for supporting their visits to the University of Colorado, Boulder.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sánchez-Oro, J., Martínez-Gavara, A., Laguna, M. et al. Variable neighborhood scatter search for the incremental graph drawing problem. Comput Optim Appl 68, 775–797 (2017). https://doi.org/10.1007/s10589-017-9926-5
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-017-9926-5