O. S. Shtogrina, O. S. Kryvenko

Read the full article 
Article in Russian


development for metagraph visualizing is made. The paper deals with issues that arise when solving the problem of metagraph visualization, such as: the placement of nodes that belong to metavertices and do not belong to them, figures intersection of metavertices. These problems are exemplified. Criteria are proposed for the final image to be considered coherent, understandable for users and corresponding to a predetermined metagraph. The problem of metagraph visualization is posed. The method based on the principles of force algorithms is proposed for the problem solving. The rules for forces between metagraph nodes are defined in the framework of the method. These forces depend on nodes type between which they are performed and the presence of edges between them. This method does not involve human intervention during the formation of the image, thus saving time at frequent changes that require rebuilding of the image. The resulting image gives the possibility to portray clearly the entities of the subject area and the links between them. Graphical analysis methods can be applied to the image. Areas for the future researches are identified. They are: minimization of the number of edges intersections and the area occupied by the resulting image. Results of the modified visualization method can improve the visual metagraph representation.

Keywords: metagraph, visualization, graph, metavertex, graphical representation

 1.     Grossman O., Harel D. On the algorithmics of higraphs. Technical Report CS97-15, Rehovot, Israel, 1997, 32 p.
2.     Basu A., Blanning R.W. Metagraphs and their applications. NY: Springer, 2006,172 p.
3.     Eades P., Lin X. Springalgorithms and symmetry. Theoretical Computer Science, 2000, vol. 240, no. 2, pp. 379–405.
4.     Eades P. A heuristic for graph drawing.Congressus Nutnerantiunt, 1984, no. 42, pp. 149–160.
5.     Fruchterman T.M.J., Reingold E.M. Graph drawing by force-directed placement. Software-Practice and Experience, 1991, vol. 21, no. 11, pp. 1129–1164.
6.     Barnes J., Hut P. A hierarchical O (N log N) force-calculation algorithm. Nature, 1986, vol. 324, no. 4, pp. 446–449. doi: 10.1038/324446a0
7.     Kamada T., Kawai S. An algorithm for drawing general undirected graphs. Information Processing Letters, 1989, vol. 31, no. 1, pp. 7–15.
8.     Hachul S., Junger M. Drawing large graphs with a potential-field-based multilevel algorithm. Lecture Notes in Computer Science, 2004, vol. 3383, pp. 285–295.
9.     Archambault D., Munzner T., Auber D. TopoLayout: Multilevel graph layout by topological features. IEEE Transactions on Visualization and Computer Graphics, 2007,vol. 13, no. 2, pp. 305–317. doi: 10.1109/TVCG.2007.46
10.  Harel D., Koren Y. A fast multi-scale method for drawing large graphs. Journal of Graph Algorithms and Applications, 2002, vol. 6, no. 3, pp. 177–202.
11.  Jin R., Xiang Y., Fuhry D., Dragan F.F. Overlapping matrix pattern visualization: A hypergraph approach. Proceedings - IEEE International Conference on Data Mining, ICDM. Pisa, Italy, 2008, art. no. 4781126, pp. 313–322. doi: 10.1109/ICDM.2008.102
12.  Paquette J., Tokuyasu T. Hypergraph visualization and enrichment statistics: How the EGAN paradigm facilitates organic discovery from big data. Proc. SPIE - The International Society for Optical Engineering, 2011, vol. 7865, art. no. 78650E. doi: 10.1117/12.890220
13.  Astanin S.V., Dragnish N.V., Zhukovsky N.K. Vlozhennye metagrafy kak modeli slozhnykh ob"ektov [Nested metagraphs as models of complex objects]. Inženernyj vestnik Dona, 2012, vol. 23, no. 4-2 (23), p. 76.
14.  Cormen T.H., Leiserson C.E., Rivest R., Stein C. Introduction to Algorithms, 2nd ed. MIT Press and McGraw Hill, 2001, 1202 p.
15.  Rogers D.F., Adams J.A. Mathematical Elements for Computer Graphics, 2nd ed. NY, McGraw-Hill, 1990, 611 p.
16.  Holten D. Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data. IEEE Transactions on Visualization and Computer Graphics, 2006, vol. 12, no. 5, pp. 741–748. doi: 10.1109/TVCG.2006.147
Copyright 2001-2017 ©
Scientific and Technical Journal
of Information Technologies, Mechanics and Optics.
All rights reserved.