Graph Drawing by High-Dimensional Embedding

Harel, David and Koren, Yehuda (2002) Graph Drawing by High-Dimensional Embedding. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 207-219 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_20).

Full text not available from this repository.

Abstract

We present a novel approach to the aesthetic drawing of undirected graphs. The method has two phases: first embed the graph in a very high dimension and then project it into the 2-D plane using principal components analysis. Running time is linear in the graph size, and experiments we have carried out show the ability of the method to draw graphs of 10^{5} in few seconds. The new method appears to have several advantages over classical methods, including a significantly better running time, a useful inherent capability to exhibit the graph in various dimensions, and an effective means for interactive exploration of large graphs.

Item Type:Conference Paper
Additional Information:10.1007/3-540-36151-0_20
Classifications:M Methods > M.999 Others
D Aesthetics > D.999 Others
P Styles > P.060 3D
P Styles > P.999 Others
ID Code:226

Repository Staff Only: item control page

References

I. Bruss and A. Frick, "Fast Interactive 3-D Graph Visualization", Proceedings of Graph Drawing 95, LNCS 1027, pp. 99-110, Springer Verlag, 1996.

T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to Algorithms, MIT Press, 1990.

G. Di Battista, P. Eades, R. Tamassia and I.G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice-Hall, 1999.

B.S. Everitt and G. Dunn, Applied Multivariate Data Analysis, Arnold, 1991.

P. Gajer, M.T. Goodrich, and S.G. Kobourov, "A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs", Proceedings of Graph Drawing 2000, LNCS 1984, pp. 211-221, Springer Verlag, 2000.

R. Hadany and D. Harel, "A Multi-Scale Method for Drawing Graphs Nicely, Discrete Applied Mathematics, 113 (2001), 3-21.

D. Harel and Y. Koren. "A Fast Multi-Scale Method for Drawing Large Graphs", Proceedings of Graph Drawing '00, LNCS 1984, pp. 183-196, Springer Verlag, 2000.

D.S. Hochbaum (ed.), Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1996.

M. Kaufmann and D. Wagner (Eds.), Drawing Graphs: Methods and Models, LNCS 2025, Springer Verlag, 2001.

Y. Koren, L. Carmen and D. Harel "ACE: A Fast Multiscale Eigenvectors Computation for Drawing Huge Graphs", to appear in Proceedings of the IEEE Symposium on Information Visualization (InfoVis) 2002.

Y. Koren, "On Spectral Graph Drawing", manuscript, 2002.

A. Quigley and P. Eades, "FADE: Graph Drawing, Clustering, and Visual Abstraction", Proceedings of Graph Drawing 2000, LNCS 1984, pp. 197-210, Springer Verlag, 2000.

D. Tunkelang, A Numerical Optimization Approach to General Graph Drawing, Ph.D. Thesis, Carnegie Mellon University, 1999.

C. Walshaw, "A Multilevel Algorithm Algorithm for Force-Directed Graph Drawing", Proceedings of Graph Drawing 2000, LNCS 1984, pp. 171-182, Springer Verlag, 2000.

D.S. Watkins, Fundamentals of Matrix Computations, John Wiley, 1991.