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, Colonial Williamsburg, VA, USA , pp. 197-210 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_19).

Full text not available from this repository.

Abstract

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
ID Code:362

Repository Staff Only: item control page

References

Richard J. Anderson, Tree data structures and n-body simulation, SIAM J. Comput. 28 (1999), no. 6, 1923-1940.

J. Barnes and P. Hut, A hierarchical o(n log n) force-calculation algorithm, Nature 324 (1986), no. 4, 446-449.

Francois Bertault, A force-directed algorithm that preserves edge crossing properties, Seventh International Symposium on Graph Drawing (Prague, Chezh Republic) (Jan Kratochvíl, ed.), Springer, September 1999, pp. 351-358.

G. Bellcoh and G. Narlikar, A practical comparison of n-body algorithms, Technical report, Wright Laboratory, 1991.

Peter Eades, A heuristic for graph drawing, Congresses Numerantium 42 (1984), 149-160.

G. Erhard, Advances in system analysis vol. 4, graphs as structural models: The application of graphs and Multigraphs in cluster analysis, Vieweg, 1988.

Q. W. Feng., Algorithms for drawing clustered graphs, Ph.D. thesis, The University of Newcastle, Australia, 1997.

T. Fruchterman and E. Reingold, Graph Drawing by force-directed placement, Software Practice and Experience 21 (1991), no. 11, 1129-1164.

Roberto Tamassia, G. Di Battista, P. Eades and I. G. Tollis, Graph drawing, algorithms for the visualization of graphs, Prentice-Hall Inc., 1999.

R. Hadany and David Harel, A multi-scale method for drawing graphs nicely, 25th International Workshop on Graph-Theoretic Concepts in Computer Science, 1999.

David Harel and Yehuda Koren, A fast multi-scale method for drawing large graphs, Technical report, Dept. of Applied Mathematics and Computer Science, Weizmann Institute, Rehovot, Israel, November 1999.

J. Hartigan, Clustering algorithms, Wiley, 1975.

W. He and K. Marriott, Constrained graph layout, Symposium on Graph Drawing, GD '96 (Stephen North, ed.), vol. 1190 of Lecture notes in Computer Science, Springer, 1996, pp. 217-232.

L. Hernquist, Hierarchical n-body methods, Computational Physics Comunications 48 (1988), 107-115.

R. W. Hockney and P. M. Sloot, Computer simulations using particles, McGrawHill, 1981.

Mao Huang, On-line animated visualization of huge graphs, Ph.D. thesis, The University of Newcastle, Australia, 1999.

Maurice M. de Ruiter Ivan Herman, Guy Melancon and Maylis Delest, Latour - a tree visualisation system, Seventh International Symposium on Graph Drawing (Prague, Chezh Republic) (Jan Kratochvíl, ed.), Springer, September 1999, pp. 392-399.

L. Greengard J. Carriert and V. Rokhlin, A fast adaptive multipole algorithm for particle simulations, SIAM Journal on Scientific Computing 9 (1988), no. 4, 669-686.

Arunabha Sen Jubin Edachery and Franz J. Brandenburg, Graph clustering using distance-k cliques, 7th International Symposium on Graph Drawing, GD '99 (Jan Kratochvíl, ed.), vol. 1731 of Lecture notes in Computer Science, Springer, 1999, pp. 98-106.

P. Eades et al K. Misue, Layout adjustment and the mental map, Journal of Visual Languages and Computing (1995), 183-210.

George Karypis and Vipin Kumar, A fats and high quality multilevel scheme for partitioning irregular graphs, SIAM Journal on Scientific Computing (1998).

_____, A parallel algorithm for multilevel graph partitioning and sparse matrix ordering, Journal of Parallel and Distributed Computing (1998).

B. W. Kerninghan and S. Lin, An efficient heuristic procedure for partitioning graphs, The Bell System Technical Journal (1970).

M. Lorr, Cluster analysis for social scientists, Jossey-Bass Ltd., 1987.

Susanne Pfalzner and Paul Gibbon, Many-body tree methods in physics, Cambridge University Press, 1996.

R. Cohen Q. W. Feng and P. Eades, How to draw a planar clustered graph, COCOON, vol. 959, Lecture Notes in Computer Science, Springer, 1995, pp. 21-31.

Reinhard Sablowski and Arne Frick, Automatic graph clustering (system demonstration), Symposium on Graph Drawing, GD '96 (Stephen North, ed.), vol. 1190 of Lecture notes in Computer Science, Springer, 1996, pp. 395-400.

Monojit Sarkar and Marc Brown, Graphical fisheye views of graphs, ACM SIGCHI '92 Conference on Human Factors in Computing Systems, March 1992.

Horst Simon and Shang-Hua Teng, How good is recursive bisection, Nasa - publication, Ames Research Center NASA, June 1993.

H. Spath, Cluster analysis algorithms for data reduction and classification of objects, Horwood, 1980.

K. Sugiyama and K. Misue, A simple and unified method for drawing graphs: Magnetic-spring algorithm, Proceedings of Graph Drawing, GD '94 (Roberto Tamassia and Ioannis Tollis, eds.), vol. 894 of Lecturte Notes in Computer Science, Springer, 1995, pp. 364-375.

S. Teng, Points spheres, and separators: A unified geometric approach to graph partitioning, Ph.D. thesis, School of Computer Science, Carnegir Mellon University, 1991.

Edward R. Tufte, The visual display of qualitative information, Garphics Press, 1983.

_____, Envisioning information, Graphics Press, 1990.

_____, Visual explanations, Graphics Press, 1997.

Daniel Tunkelang, Jiggle: Java interactive general graph layout environment, Sixth International Symposium on Graph DRawing (McGill University, Canada) (Sue International Symposium on Graph Drawing (McGill University, Canada) (Sue Whitesides, ed.), Springer, August 1998.

Andrej Mrvar Vladimir Batagelj and Matjaz Zaversnik, Partitioning approach to visualization of large graphs, 7th International Symposium on Graph Drawing, GD '99 (Jan Kratochvil, ed.), vol. 1731 of Lecture Notes in Computer Science, Springer, 1999, pp. 90-97.

#Jiong Yang Wei Wang and Richard Muntz, Sting: A statistical information grid approach to spatial data mining, 23rd International Conference on Very Large Data Bases(VLDB), IEEE, 1997, pp. 186-195.

_____, Sting+: An approach to active spatial data mining, IEEE, 1999, pp. 116-125.