Evaluation of graph layout algorithms for visualizing graph patterns

OData support
Dr. Ujhelyi Zoltán
Department of Measurement and Information Systems

Model driven development is spreading widely in the world of software development. This method emphasizes the creation of a system’s model. The complete model of a system developed with the model driven method often contains too much elements to easily comprehend it. This can be helped by model queries. With the use of properly defined declarative constraints the complete model can be reduced to a submodel with smaller number of elements. This results in a more understandable subset of the complete model. More than often the graphical representation of the subset which corresponds with the drawing of graphs, in opposition with the text based representation, is more comprehendible for the human brain.

For the creation of models the most widely used tool is the Eclipse based Eclipse Modeling Framework. Because of the EMF-IncQuery plug-in, developed by the Department of Measurement and Information Systems, we can define model queries. These queries could be represented as graphs using Zest. With the Zest plug-in we can illustrate graphs furthermore we can use the previously defined layout algorithms included in the plug-in. Although using these algorithms does not guarantee a good result.

The graphs corresponding with models can be widely different depending on the system. Because of this a layout algorithm can provide a suitable result for a subgraph but not for another. The Zest makes it possible to implement new layout algorithms which can be specified to a given graph. Furthermore the already existing algorithms can be extended with model specific details or parts which the user would generalize to all graphs.

In my thesis I am examining the layout algorithms included in Zest and I am presenting the extended Sugiyama algorithm. The new heuristics I implemented are able to obtain better results which are also shown. The creation of these extensions was in consideration of being used by other layout algorithms.


Please sign in to download the files of this thesis.