Years and Authors of Summarized Original Work
1963; Tutte
1984; Eades
Problem Definition
Given a connected undirected graph, the problem is to determine a straight-line layout such that the structure of the graph is represented in a readable and unbiased way. Part of the problem is the definition of readable and unbiased.
Formally, we are given a simple, undirected graph G = (V, E) with vertex set V and edge set \(E \subseteq \binom{V }{2}\). Let n = | V | be the number of vertices and m = | E | the number of edges. The neighbors of a vertex v are defined as N(v) = { u : { u, v} ∈ E}, and \(\deg (v) = \vert N(v)\vert \) is its degree. We assume that G is connected, for otherwise the connected components can be treated separately.
A (two-dimensional) layout for G is a vector p = (p v ) v ∈ V of vertex positions \(p_{v} =\langle x_{y},y_{v}\rangle \in\mathbb{R}^{2}\). Since edges are drawn as line segments, the drawing is completely determined by these vertex positions. All approaches...
Recommended Reading
Brandes U (2001) Drawing on physical analogies. In: Kaufmann M, Wagner D (eds) Drawing graphs: methods and models. Lecture notes in computer science, vol 2025. Springer, Berlin/Heidelberg, pp 71–86
Brandes U, Pich C (2009) An experimental study on distance-based graph drawing. In: Proceedings of the 16th international symposium on graph drawing (GD’08), Heraklion. Lecture notes in computer science, vol 5417. Springer, pp 218–229
Chen L, Buja A (2013) Stress functions for nonlinear dimension reduction, proximity analysis, and graph drawing. J Mach Learn Res 14:1145–1173
Eades P (1984) A heuristic for graph drawing. Congr Numerantium 42:149–160
Fruchterman TMJ, Reingold EM (1991) Graph drawing by force-directed placement. Softw Pract Exp 21(11):1129–1164
Gansner ER, Koren Y, North SC (2005) Graph drawing by stress majorization. In: Proceedings of the 12th international symposium on graph drawing (GD’04), New York. Lecture notes in computer science, vol 3383. Springer, New York, pp 239–250. doi: 10.1007/978-3-540-31843-9_25
Hall KM (1970) An r-dimensional quadratic placement algorithm. Manag Sci 17(3):219–229
Kamada T, Kawai S (1989) An algorithm for drawing general undirected graphs. Inf Process Lett 31:7–15
Kirchhoff GR (1847) Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird. Ann Phys Chem 72:497–508
Kobourov SG (2013) Force-directed drawing algorithms. In: Tamassia R (ed) Handbook of graph drawing and visualization. CRC, Boca Raton, pp 383–408
Koren Y (2005) Drawing graphs by eigenvectors: theory and practice. Comput Math Appl 49(11–12):1867–1888. doi:10.1016/j.camwa.2004.08.015
Kruskal JB (1964) Multidimensional scaling for optimizing goodness of fit to a nonmetric hypothesis. Psychometrika 29(1):1–27
de Leeuw J (1977) Applications of convex analysis to multidimensional scaling. In: Barra JR, Brodeau F, Romier G, van Cutsem B (eds) Recent developments in statistics. North-Holland, Amsterdam, pp 133–145
Noack A (2009) Modularity clustering is force-directed layout. Phys Rev E 79:026,102
Tutte WT (1963) How to draw a graph. Proc Lond Math Soc 13(3):743–768
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer Science+Business Media New York
About this entry
Cite this entry
Brandes, U. (2014). Force-Directed Graph Drawing. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, Boston, MA. https://doi.org/10.1007/978-3-642-27848-8_648-1
Download citation
DOI: https://doi.org/10.1007/978-3-642-27848-8_648-1
Received:
Accepted:
Published:
Publisher Name: Springer, Boston, MA
Online ISBN: 978-3-642-27848-8
eBook Packages: Springer Reference Computer SciencesReference Module Computer Science and Engineering