טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentFrishman Yaniv
SubjectGraph Drawing Algorithms in Information Visualization
DepartmentDepartment of Computer Science
Supervisor Professor Ayellet Tal
Full Thesis textFull thesis text - English Version


Abstract

Information Visualization is the use of computer-supported, interactive, visual representations of data, and in particular, abstract data, to amplify cognition. Graph drawing addresses the problem of creating geometric representations of graphs.


This thesis addresses several related problems in graph drawing. First, we address the problem of quickly creating a layout of a large, general graph. We devise a multi-level algorithm which is based on spectral partitioning. The algorithm is able to produce aesthetic layouts at a fraction of the time of existing algorithms. Next, we discuss an algorithm for improving an existing layout. This is done by warping the coordinates of the nodes, thus making use of empty and sparse regions in the image of the layout. We then turn out attention to dynamic graph drawing. The challenge here is to compute a stable and aesthetic layout while still making it easy for the user to comprehend the changes. First, we present a multi-level online incremental algorithm for drawing general graphs. Assigning different movement flexibilities to the nodes of the graph allows efficiently creating a stable layout. Next, we discuss an online dynamic algorithm for drawing graphs which contain an inherent grouping into clusters. The algorithm uses node pinning, invisible spacer nodes and edge lengths and weights in order to minimize changes to the clustered structure of the graph.


In recent years, the programmability and computational power of commodity graphics processing units (GPUs) has increased tremendously. GPUs, traditionally used for graphics-related applications are now being employed in many data-parallel problems. Unlike matrices and images, graphs are unstructured and hence graph layout does not seem to be suitable for acceleration on the GPU. In this research we discuss how to accelerate static layout, dynamic layout and graph improvement algorithms using a GPU. 


The algorithms developed during this research have been used in different information visualization applications. We visualize the structure of the networks of Internet service providers. We improve graphs computed by various state of the art algorithms on several applications, including bioinformatics, social interactions and finite element meshes. We study social networks and the evolution of discussion threads in Internet sites. Finally, we visualize mobile object frameworks using dynamic clustered graph drawing. In these frameworks objects migrate between hosts while the application is running. An innovative, graph-based, scalable, focus + context visualization depicts both the physical network of machines and the logical network of ties between mobile objects.