Evaluation of graph layout algorithms

OData support
Supervisor:
Ujhelyi Zoltán
Department of Measurement and Information Systems

Abstract

In various sciences for modeling information, relations and processes in many cases graphs are most appropriate. Despite their simplicity, we can describe diverse and complex models with them, what is done using different text languages, object-oriented classes and other computer-processed technique. Because the graph models describe only the structure, to simplify and facilitate reading graph models we need to draw them using a layout algorithm.

In this thesis I present a framework for evaluating various graph layout algorithms. My goal is to understand the behavior of graph layout algorithms, the graph model and the algorithm parameters. Such parameters are the number of iteration steps or the bounds of the drawing area.

We can measure the quality of the layout based on static and dynamic aspects. A static criterion characterizes a drawing of the graph. Such as minimizing the edge intersections and the node overlaps. The dynamic behavior determines the degree of change in the layout, if we bring change to the graph model or algorithm configuration.

To perform the analysis I created a test environment which allows applying the layout algorithms to various graph models with different configurations and counting static and dynamic metrics. It is possible to modify the graph model and the algorithm parameters so we can examine the algorithm’s dynamic behavior.

I demonstrate the usability of such layout evaluating by examine three different algorithms. The results show the effect of changes the parameters. Using these results we can configure the layout algorithms with consider its dynamic behavior.

Downloads

Please sign in to download the files of this thesis.