Investigation Into Edge Bundling For Visualizing Large Graphs

The rapid increasing of data size is challenging the usefulness of graph visualization, notably in the form of the node-link diagrams. Edge bundling has been widely used to reduce visual clutter and reveal high-level edge patterns for large graphs. It aggregates similar edges and forms the so-called bundles. These bundles,which can be recognized independently, reduces visual complexity and reveals high-level structure, i.e. skeleton or backbones, which is crucial for understanding the underlying pattern of data. Several edge bundling approaches have been published in the literature, based on diverse technique paradigms, e.g. force-directed model,geometry structure, edge routing, image skeleton extraction, etc. The results from existing approaches generally show strong edge attraction, bundles with unnecessary curvature and tangling at bundle intersections. Inappropriate bundling may fail to reveal true data patterns and even mislead users.This thesis summarizes the related literature and proposes the three goals of edge bundling, i.e. revealing skeleton or backbone structure, generating distinguishable bundles and facilitating traceability of bundles as much as possible. To realize the goals, we present a parameterized 6-step edge bundling approach called LEB, i.e.layered edge bundling. LEB divides edges into layers based on their directions and routes them independently to avoid mutual interferences. Thanks to applying regular grid space partition with large granularity and parameterized A* routing algorithm,the rendering results show distinguishable and traceable bundles and thus revealing the graph structure. We also propose a simple yet effective bundle recognition and coloring method that takes full advantage of the results from earlier steps and enhances the visualization. The bundling results by LEB are adjustable by tuning a small number of parameters. We discuss their initial settings, roles and adjustment methods respectively.We have implemented LEB using web-based techniques in JavaScript. Thanks to route reuse,our implementation avoids a large number of redundant computation,relating the computational complexity only to the grid granularity rather than the data size. A performance test is conducted on three published datasets, i.e. US migration dataset,US airline dataset and TVCG citation dataset. The results show that LEB is sufficiently efficient to support real-time interaction without hardware/software acceleration, e.g. GPU-acceleration or multithreading. The rendering results also demonstrate that LEB achieves the three goals with both fixed and flexible node layouts.Finally, to evaluate and compare LEB with previous approaches, we conduct a user experiment, where subjects are asked to depict the backbones of visualization images with a given number of strokes. We use and model the stroke coverage as performance measurement. The statistical analysis demonstrates LEB's superiority over previous approaches on all datasets. There has been no usability evaluation of edge bundling in the literature.