Abstract
With shortest-path distances as input, classical multidimensional scaling can be regarded as a spectral graph drawing algorithm, and recent approximation techniques make it scale to very large graphs. In comparison with other methods, however, it is considered inflexible and prone to degenerate layouts for some classes of graphs.
We want to challenge this belief by demonstrating that the method can be flexibly adapted to provide focus+context layouts. Moreover, we propose an alternative instantiation that appears to be more suitable for graph drawing and prevents certain degeneracies.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bavaud, F.: On the Schoenberg transformations in data analysis: Theory and illustrations. Journal of Classification 28(3), 297–314 (2011)
Borg, I., Groenen, P.: Modern Multidimensional Scaling: Theory and Applications. Springer (2005)
Brandes, U., Pich, C.: Eigensolver Methods for Progressive Multidimensional Scaling of Large Data. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 42–53. Springer, Heidelberg (2007)
Brandes, U., Pich, C.: An Experimental Study on Distance-Based Graph Drawing. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 218–229. Springer, Heidelberg (2009)
Buja, A., Swayne, D.F., Littmann, M.L., Dean, N., Hofmann, H.: Xgvis: Interactive data visualization with mds. Journal of Computational and Graphical Statistics (2001)
Card, S.K., Mackinlay, J.D., Shneiderman, B. (eds.): Readings in Info. Vis.: Using Vision to Think. Morgan Kaufman Publishers (1999)
Civril, A., Magdon-Ismail, M., Bocek-Rivele, E.: SDE: Graph Drawing Using Spectral Distance Embedding. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 512–513. Springer, Heidelberg (2006)
Çivril, A., Magdon-Ismail, M., Bocek-Rivele, E.: SSDE: Fast Graph Drawing Using Sampled Spectral Distance Embedding. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 30–41. Springer, Heidelberg (2007)
Cox, T., Cox, M.: Multidimensional Scaling. CRC/Chapman and Hall (2001)
France, S.L., Carroll, J.D.: Two-way multidimensional scaling: A review. IEEE Trans. Sys., Man, and Cyber., Part C: Apps. and Reviews 41(5), 644–661 (2011)
Furnas, G.W.: Generalized fisheye views. In: Proc. ACM SIGCHI Conf. Human Factors in Comp. Sys., pp. 16–23. ACM Press (1986)
Gajer, P., Goodrich, M.T., Kobourov, S.G.: A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 211–221. Springer, Heidelberg (2001)
Gansner, E., Koren, Y., North, S.: Topological fisheye views for visualizing large graphs. IEEE Trans. Vis. and Comp. Graph. 11(4), 457–468 (2005)
Gansner, E.R., Koren, Y., North, S.: Graph Drawing by Stress Majorization. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 239–250. Springer, Heidelberg (2005)
Gower, J.C.: Some distance properties of latent root and vector methods used in multivariate analysis. Biometrika 53, 325–338 (1966)
Gower, J.C.: Euclidean distance geometry. Math. Scientist. 7, 1–14 (1982)
Gower, J.C.: Properties of Euclidean and non-Euclidean distance matrices. Linear Algebra and Its Applications 67, 81–97 (1985)
Hall, K.M.: An r-dimensional quadratic placement algorithm. Management Science 17, 219–229 (1970)
Harel, D., Koren, Y.: Graph Drawing by High-Dimensional Embedding. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 207–219. Springer, Heidelberg (2002)
Hosobe, H.: A high-dimensional approach to interactive graph visualization. In: Proc. of ACM Symp. on Applied Comp., pp. 1253–1257. ACM (2004)
Hosobe, H.: An extended high-dimensional method for interactive graph drawing. In: Proc. of the Asia-Pac. Info. Vis., pp. 15–20. Austral. Comp. Soc. (2005)
Kaugars, K., Reinfelds, J., Brazma, A.: A Simple Algorithm for Drawing Large Graphs on Small Screens. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 278–281. Springer, Heidelberg (1995)
Keahey, T.A., Robertson, E.L.: Techniques for non-linear magnification transformations. In: Proc. IEEE Symp. Info. Vis., pp. 38–46. IEEE Comp. Soc. (1996)
Koren, Y., Carmel, L.: Visualization of labeled data using linear transformations. In: Proc. IEEE Symp. Info. Vis., pp. 121–128. IEEE Comp. Soc. (2003)
Koren, Y., Carmel, L.: Robust linear dimensionality reduction. IEEE Trans. Vis. and Compr. Graph. 10(4), 459–470 (2004)
Kruskal, J.B., Seery, J.B.: Designing network diagrams. In: Proc. of the 1st Gen. Conf. on Soc. Graph., pp. 22–50 (1980)
Misue, K., Sugiyama, K.: Multi-viewpoint perspective display methods: Formulation and application to compound graphs. In: Proc. Conf. on HCI, pp. 834–838. Elsevier (1991)
Sarkar, M., Brown, M.H.: Graphical fisheye views of graphs. In: Proc. Conf. on HCI, pp. 83–91. ACM (1992)
de Silva, V., Tenenbaum, J.B.: Global versus local methods in nonlinear dimensionality reduction. In: Adv. Neur. Info. Process. Sys., vol. 15, pp. 705–712. MIT Press (2003)
Storey, M.D., David Fracchia, F., Mueller, H.A.: Customizing a fisheye view algorithm to preserve the mental map. Jour. Vis. Lang. Comp. 10(3), 245–267 (1999)
Torgerson, W.S.: Multidimensional scaling: I. Theory and method. Psychometrika 17(4), 401–419 (1952)
Tzeng, J., Lu, H.H.S., Li, W.H.: Multidimensional scaling for large genomic datasets. BMC Bioinformatics 9(1), 179–197 (2008)
Webb, A.R.: Statistical Pattern Recognition. John Wiley & Sons (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Klimenta, M., Brandes, U. (2013). Graph Drawing by Classical Multidimensional Scaling: New Perspectives. In: Didimo, W., Patrignani, M. (eds) Graph Drawing. GD 2012. Lecture Notes in Computer Science, vol 7704. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36763-2_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-36763-2_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36762-5
Online ISBN: 978-3-642-36763-2
eBook Packages: Computer ScienceComputer Science (R0)