A Potential-Field-Based Multilevel Algorithm

I would like to thank everyone who supported me in writing this thesis. In particular, many thanks are addressed to my supervisor Prof. Dr. Michael J¨unger for giving me the possibility to research in the field of force-directed graph drawing and for the constructive and helpful discussions in the internal seminars. I am very grateful to Dr. Sebastian Leipert for bringing me to the research field of automatic graph drawing and to HD Dr. Bert Randerath and Claudia Schlesiger for their proof-reading.

Many thanks go to Thomas Lange, Constantin Hellweg, Holger Flier, and Annette Menze for supporting me in all technical questions. Without their assistance and profes- sional work, this dissertation would probably still be in progress. I thank Michael Belling and Ursula Neugebauer for helping me in the acquisition of literature and all administrative processes. A big thank goes also to Dr. Christoph Buchheim, Matthias Elf, Dr. Frauke Liers, Merijam Percan, and all previous mentioned colleagues for their “open doors” in the last years in Cologne. Furthermore, I would like to thank Yehuda Koren, Daniel Tunkelang, and Roman Yusufov for making me available the implementations of their algorithms. Finally, I am very grateful to my girlfriend Claudia Schlesiger and my parents Gerda Hachul and Paul Hachul for supporting me in all aspects of my life. Abstract The aim of automatic graph drawing is to compute a well-readable layout of a given graph G = (V,E). One very popular class of algorithms for drawing general graphs are force- directed methods. These methods generate drawings of G in the plane so that each edge is represented by a straight line connecting its two adjacent nodes. The computation of the drawings is based on associating G with a physical model. Then, the algorithms iteratively try to find a placement of the nodes so that the total energy of the physical system is minimal. Several force-directed methods can visualize large graphs containing many thousands of vertices in reasonable time. However, only some of these methods guarantee a sub-quadratic running time in special cases or under certain assumptions, but not in general. The others are not sub-quadratic at all. We develop a new force-directed algorithm that is based on a combination of an effi- cient multilevel strategy and a method for approximating the repulsive forces in the system by rapidly evaluating potential fields. The worst-case running time of the new method is O(|V|log|V|+|E|) with linear memory requirements. In practice, the algorithm generates nice drawings of graphs containing up to 100000 nodes in less than five minutes. Fur- thermore, it clearly visualizes even the structures of those graphs that turned...

Website: kups.ub.uni-koeln.de | Filesize: -
No of Page(s): 198
Download A Potential-Field-Based Multilevel Algorithm for ... - Universität zu Köln.pdf