Analysis of algorithms for automatic arrangement of entities and construction of communications

Authors: Kiriakov E.A., Levinskiy A.T.
Published in issue: #4(33)/2019
DOI: 10.18698/2541-8009-2019-4-469
Category: Informatics, Computer Engineering and Control | Chapter: System Analysis, Control, and Information Processing, Statistics
Keywords: algorithm, automation, connections, constructions, genetic algorithm, model, genetic, analytical, mutation, arrangement of entities, construction of connections
Published: 30.04.2019

It is often convenient to study large systems using conceptual diagrams (for example, entity-relationship diagrams or UML). For the automatic construction of such diagrams, algorithms for the automatic arrangement of entities and automatic construction of links are required. In this connection, an analysis was made of the existing algorithms for the automatic arrangement of entities and the automatic construction of links. There are three main groups of algorithms: algorithms based on the physical model, analytical algorithms and genetic algorithms. For each group of algorithms, basic information was transmitted; the pros and cons of each group of algorithms are listed. In addition, several specific algorithms are analyzed for each group of algorithms. The study of the materials of this article will give readers a basic knowledge of the main groups of algorithms and help to understand the principle of their work.

References

[1] Sokolov G.V. Analysis of automatic graph drawing on a plane within the scope of model visualization problem at the graphs. Vestnik Permskogo Gosudarstvennogo Tekhnicheskogo Universiteta. Prikladnaya matematika i mekhanika [Perm State Technical University Bulletin. Applied Mathematics and Mechanics], 2008, no. 15, pp. 162–171 (in Russ.).

[2] Dickerson M., Eppstein D., Goodrich M.T., et al. Confluent drawings: visualizing non-planar diagrams in a planar way. JGAA, 2005, vol.9, no. 1, pp. 31–52. DOI: 10.7155/jgaa.00099 URL: http://jgaa.info/getPaper?id=99

[3] Gladkov L.A. Solution of the problem of graph planarization on basis bionic technologies. Vestnik yuzhnogo nauchnogo tsentra RAN [Vestnik SSC RAS], 2005, vol. 1, no. 2, pp. 51–57 (in Russ.).

[4] Davis L.D. Handbook of genetic algorithms. Van Nostrand Reinold, 1991.

[5] Nikolov N.S., Tarassov A. Graph layering by promotion of nodes. Discrete Appl. Math., 2006, vol. 154, no. 5, pp. 848–860. DOI: 10.1016/j.dam.2005.05.023 URL: https://www.sciencedirect.com/science/article/pii/S0166218X05003100

[6] Siirtola H., Makinen E. The Barycenter heuristic and the reorderable matrix. Informatica, 2005, vol. 29, no. 3, p. 357–364.

[7] Carstens J.J. Node and label placement in a layered layout algorithm. Master Thesis. University of Kiel, 2012.

[8] Patarasuk P., Whalley D. Crossing reduction for layered hierarchical graph drawing. Master Thesis. Florida State University, 2004.

[9] Genc B., Dogrusoz U. An algorithm for automated layout of process description maps drawn in SBGN. Bioinformatics, 2016, vol. 32, no. 1, pp. 77–84. DOI: 10.1093/bioinformatics/btv516 URL: https://academic.oup.com/bioinformatics/article/32/1/77/1742665

[10] Aho A.V., Ullman J.D., Hopcroft J.E. Data structures and algorithms. Pearson, 1983. (Russ. ed.: Struktury dannykh i algoritmy. Moscow, Vil’yams Publ., 2000.)