Editing Force-directed graph drawing (section)

==Disadvantages==
The main disadvantages of force-directed algorithms include the following:
; High [[Time complexity|running time]]: The typical force-directed algorithms are in general ''considered'' to run in cubic time (<math>O(n^3)</math>), where <math>n</math> is the number of nodes of the input graph. This is because the number of iterations is estimated to be linear (<math>O(n)</math>), and in every iteration, all pairs of nodes need to be visited and their mutual repulsive forces computed. This is related to the [[N-body problem]] in physics. However, since repulsive forces are local in nature the graph can be partitioned such that only neighboring vertices are considered. Common techniques used by algorithms for determining the layout of large graphs include high-dimensional embedding,<ref>{{citation
  | last1=Harel | first1=David | author1-link = David Harel
  | last2=Koren | first2=Yehuda
  | contribution=Graph drawing by high-dimensional embedding
  | year=2002
  | title=Proceedings of the 9th International Symposium on Graph Drawing
  | pages=207&ndash;219
  | publisher=Springer | isbn=3-540-00158-1| citeseerx=10.1.1.20.5390 }}</ref> multi-layer drawing and other methods related to [[N-body simulation]]. For example, the [[Barnes–Hut simulation]]-based method FADE<ref name="quigley+eades">{{citation
 |last1        = Quigley
 |first1       = Aaron
 |last2        = Eades
 |first2       = Peter
 |author2-link = Peter Eades
 |contribution = FADE: Graph Drawing, Clustering, and Visual Abstraction
 |url          = https://aaronquigley.org/wp-content/uploads/2019/03/Fade-2000-aquigley.pdf 
 |year         = 2001
 |title        = Proceedings of the 8th International Symposium on Graph Drawing
 |pages        = 197&ndash;210
 |isbn         = 3-540-41554-8
 }}.</ref> can improve the running time to be linearithmic, or <math>n\log(n)</math> per iteration. As a rough guide, in a few seconds one can expect to draw at most 1,000 nodes with a standard <math>n^2</math> per iteration technique, and 100,000 with a <math>n\log(n)</math> per iteration technique.<ref name="quigley+eades" /> Force-directed algorithms, when combined with a graph clustering approach, can draw graphs of millions of nodes.<ref>{{citation|title=A Gallery of Large Graphs|url=http://yifanhu.net/GALLERY/GRAPHS/|access-date=22 Oct 2017}}</ref>

; Poor local minima: It is easy to see that force-directed algorithms produce a graph with minimal energy, in particular one whose total energy is only a [[local minimum]]. The local minimum found can be, in many cases, considerably worse than a global minimum, which translates into a low-quality drawing. For many algorithms, especially the ones that allow only ''down-hill'' moves of the vertices, the final result can be strongly influenced by the initial layout, that in most cases is randomly generated. The problem of poor local minima becomes more important as the number of vertices of the graph increases. A combined application of different algorithms is helpful to solve this problem.<ref>{{citation
 | last1 = Collberg | first1 = Christian
 | last2 = Kobourov | first2 = Stephen
 | last3 = Nagra | first3 = Jasvir
 | last4 = Pitts | first4 = Jacob
 | last5 = Wampler | first5 = Kevin
 | contribution = A System for Graph-based Visualization of the Evolution of Software
 | doi = 10.1145/774833.774844
 | isbn = 1-58113-642-0
 | location = New York, NY, USA
 | pages = 77–86; figures on p.&nbsp;212
 | publisher = ACM
 | title = Proceedings of the 2003 ACM Symposium on Software Visualization (SoftVis '03)
 | url = https://www.researchgate.net/publication/2851716
 | year = 2003| s2cid = 824991
 |quote=To achieve an aesthetically pleasing layout of the graph it is also necessary to employ modified Fruchterman–Reingold forces, as the Kamada–Kawai method does not achieve satisfactory methods by itself but rather creates a good approximate layout so that the Fruchterman-Reingold calculations can quickly "tidy up" the layout.}}</ref> For example, using the Kamada–Kawai algorithm<ref name="kk89"/> to quickly generate a reasonable initial layout and then the Fruchterman–Reingold algorithm<ref name="fr91"/> to improve the placement of neighbouring nodes. Another technique to achieve a global minimum is to use a multilevel approach.<ref>{{citation
 | last = Walshaw | first = Chris
 | doi = 10.7155/jgaa.00070
 | issue = 3
 | journal = Journal of Graph Algorithms and Applications
 | mr = 2112231
 | pages = 253–285
 | title = A multilevel algorithm for force-directed graph-drawing
 | volume = 7
 | year = 2003}}</ref>