Novel heurisitic approaches to iterative graph drawing

This thesis presents a new graph drawing approach (the concentric approach) for drawing any undirected graph without taking stress or forces into account, in order to address the trade-off between quality and running time. This approach, unlike the widely-used force-directed graph drawing algorithms, does not need to calculate the Cartesian distances between pairs of nodes in order to calculate forces or stresses. Also, the concentric approach does not need to calculate eigenvalues or eigenvectors of any matrix as is required in the state-of-the-art spectral layout algorithms. Our approach is, at the same time, similar to the class of force-directed algorithms in the sense that it is an iterative-scheme approach that updates node positions at each iteration. The proposed approach incorporates two independent models in order to deal with two different graph representations: the adjacency matrix and the distance matrix. A distance matrix is easily extensible to a similarity/dissimilarity matrix, so that multidimensional data can be visualized as well. We compare each of our graph drawing models with the algorithms most similar to them and present our results (in terms of both running time and visual layouts) in order to evaluate the performance improvement. This is found to be significant in both cases. Our running time improvement is in the order of 5:1 for the two graph drawings models, while the layout improvement is measured qualitatively. We also propose the use of pre-processing evolutionary algorithms in order to improve the quality of some specific types of small graphs when drawn by any iterative graph drawing algorithm, including the ones discussed in this thesis. The use of these algorithms, is shown to demonstrate a significant improvement of the quality of some specific types of graphs. The overall conclusion of this thesis is, first of all, that our concentric approach can successfully deal with the trade-off between quality and running time. Secondly, we propose several pre-processing methods which significantly improve the layout quality for some specific types of graphs when drawn by any iterative graph drawing algorithm.