FADE: Graph Drawing, Clustering, and Visual Abstraction

Quigley, Aaron and Eades, Peter (2001) FADE: Graph Drawing, Clustering, and Visual Abstraction. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000 , pp. 197-210(Official URL: http://dx.doi.org/10.1007/3-540-44541-2_19).

Full text not available from this repository.


A fast algorithm(FADE ) for the 2D drawing, geometric clustering and multilevel viewing of large undirected graphs is presented. The algorithm is an extension of the Barnes-Hut hierarchical space decomposition method, which includes edges and multilevel visual abstraction. Compared to the original force directed algorithm, the time overhead is $O(e + n \log n)$ where n and e are the numbers of nodes and edges. The improvement is possible since the decomposition tree provides a systematic way to determine the degree of closeness between nodes without explicitly calculating the distance between each node. Different types of regular decomposition trees are introduced. The decomposition tree also represents a hierarchical clustering of the nodes, which improves in a graph theoretic sense as the graph drawing approaches a lower energy state. Finally, the decomposition tree provides a mechanism to view the hierarchical clustering on various levels of abstraction. Larger graphs can be represented more concisely, on a higher level of abstraction, with fewer graphics on screen.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-44541-2_19
Classifications: M Methods > M.999 Others
P Styles > P.180 Cluster
M Methods > M.400 Force-directed / Energy-based
G Algorithms and Complexity > G.350 Clusters
P Styles > P.999 Others
URI: http://gdea.informatik.uni-koeln.de/id/eprint/362

Actions (login required)

View Item View Item