Editing Force-directed graph drawing (section)

==History==
Force-directed methods in graph drawing date back to the work of {{harvtxt|Tutte|1963}}, who showed that [[polyhedral graph]]s may be drawn in the plane with all faces convex by fixing the vertices of the outer face of a planar embedding of the graph into [[convex position]], placing a spring-like attractive force on each edge, and letting the system settle into an equilibrium.<ref>{{citation|first=W. T.|last=Tutte|author-link=W. T. Tutte|title=How to draw a graph|journal=Proceedings of the London Mathematical Society|volume=13|issue=52|pages=743–768|year=1963|doi=10.1112/plms/s3-13.1.743}}.</ref> Because of the simple nature of the forces in this case, the system cannot get stuck in local minima, but rather converges to a unique global optimum configuration. Because of this work, embeddings of planar graphs with convex faces are sometimes called [[Tutte embedding]]s.

The combination of attractive forces on adjacent vertices, and repulsive forces on all vertices, was first used by {{harvtxt|Eades|1984}};<ref>{{citation
  | last=Eades | first=Peter | author-link = Peter Eades
  | title=A Heuristic for Graph Drawing
  | year=1984
  | journal=Congressus Numerantium
  | volume=42 | issue=11 | pages=149–160}}.</ref> additional pioneering work on this type of force-directed layout was done by {{harvtxt|Fruchterman|Reingold|1991}}.<ref name="fr91">{{citation
  | last1=Fruchterman | first1=Thomas M. J.
  | last2=Reingold | first2=Edward M. | author2-link = Edward Reingold
  | title=Graph Drawing by Force-Directed Placement
  | year=1991
  | journal=Software: Practice and Experience
  | publisher=Wiley
  | volume=21 | issue=11 | pages=1129&ndash;1164
  | doi=10.1002/spe.4380211102| s2cid=31468174
 }}.</ref> The idea of using only spring forces between all pairs of vertices, with ideal spring lengths equal to the vertices' graph-theoretic distance, is from {{harvtxt|Kamada|Kawai|1989}}.<ref name="kk89">{{citation
  | last1=Kamada | first1=Tomihisa
  | last2=Kawai | first2=Satoru
  | title=An algorithm for drawing general undirected graphs
  | year=1989
  | journal=Information Processing Letters
  | publisher=Elsevier
  | volume=31 | issue=1 | pages=7&ndash;15
  | doi=10.1016/0020-0190(89)90102-6}}.</ref>