28:
20:
576:, placing a spring-like attractive force on each edge, and letting the system settle into an equilibrium. 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
320:. Monotonic convergence, the property that the algorithm will at each iteration decrease the stress or cost of the layout, is important because it guarantees that the layout will eventually reach a local minimum and stop. Damping schedules cause the algorithm to stop, but cannot guarantee that a true local minimum is reached.
288:
Another advantage of this class of algorithm is the interactive aspect. By drawing the intermediate stages of the graph, the user can follow how the graph evolves, seeing it unfold from a tangled mess into a good-looking configuration. In some interactive graph drawing tools, the user can pull one or
265:
Force-directed algorithms can be easily adapted and extended to fulfill additional aesthetic criteria. This makes them the most versatile class of graph drawing algorithms. Examples of existing extensions include the ones for directed graphs, 3D graph drawing, cluster graph drawing, constrained graph
258:
At least for graphs of medium size (up to 50–500 vertices), the results obtained have usually very good quality based on the following criteria: uniform edge length, uniform vertex distribution and showing symmetry. This last criterion is among the most important ones and is hard to achieve with any
208:
Once the forces on the nodes and edges of a graph have been defined, the behavior of the entire graph under these sources may then be simulated as if it were a physical system. In such a simulation, the forces are applied to the nodes, pulling them closer together or pushing them further apart. This
50:
in two-dimensional or three-dimensional space so that all the edges are of more or less equal length and there are as few crossing edges as possible, by assigning forces among the set of edges and the set of nodes, based on their relative positions, and then using these forces either to simulate the
90:
for this system of forces, the edges tend to have uniform length (because of the spring forces), and nodes that are not connected by an edge tend to be drawn further apart (because of the electrical repulsion). Edge attraction and vertex repulsion forces may be defined using functions that are not
554:
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
432:
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, multi-layer drawing and other methods
955:
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
555:
solve this problem. For example, using the Kamada–Kawai algorithm to quickly generate a reasonable initial layout and then the
Fruchterman–Reingold algorithm to improve the placement of neighbouring nodes. Another technique to achieve a global minimum is to use a multilevel approach.
175:
A force-directed graph can involve forces other than mechanical springs and electrical repulsion. A force analogous to gravity may be used to pull vertices towards a fixed point of the drawing space; this may be used to pull together different
303:
force-directed algorithms often appear in the literature and in practice (because they are relatively easy to understand), more reasoned approaches are starting to gain traction. Statisticians have been solving similar problems in
282:
Typical force-directed algorithms are simple and can be implemented in a few lines of code. Other classes of graph-drawing algorithms, like the ones for orthogonal layouts, are usually much more involved.
231:
It is also possible to employ mechanisms that search more directly for energy minima, either instead of or in conjunction with physical simulation. Such mechanisms, which are examples of general
188:
may be used for directed graphs. Repulsive forces may be placed on edges as well as on nodes in order to avoid overlap or near-overlap in the final drawing. In drawings with curved edges such as
272:
Since they are based on physical analogies of common objects, like springs, the behavior of the algorithms is relatively easy to predict and understand. This is not the case with other types of
550:. 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
213:
state; i.e., their relative positions do not change anymore from one iteration to the next. The positions of the nodes in this equilibrium are used to generate a drawing of the graph.
154:
91:
based on the physical behavior of springs and particles; for instance, some force-directed systems use springs whose attractive force is logarithmic rather than linear.
536:
474:
377:
54:
While graph drawing can be a difficult problem, force-directed algorithms, being physical simulations, usually require no special knowledge about graph theory such as
501:
124:
921:
Collberg, Christian; Kobourov, Stephen; Nagra, Jasvir; Pitts, Jacob; Wampler, Kevin (2003), "A System for Graph-based
Visualization of the Evolution of Software",
426:
397:
591:. 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
180:
of a disconnected graph, which would otherwise tend to fly apart from each other because of the repulsive forces, and to draw nodes with greater
538:
per iteration technique. Force-directed algorithms, when combined with a graph clustering approach, can draw graphs of millions of nodes.
289:
more nodes out of their equilibrium state and watch them migrate back into position. This makes them a preferred choice for dynamic and
613:, an interactive visualization and exploration platform for all kinds of networks and complex systems, dynamic and hierarchical graphs.
546:
It is easy to see that force-directed algorithms produce a graph with minimal energy, in particular one whose total energy is only a
428:), and in every iteration, all pairs of nodes need to be visited and their mutual repulsive forces computed. This is related to the
78:
are used to attract pairs of endpoints of the graph's edges towards each other, while simultaneously repulsive forces like those of
619:, software that implements a multilevel force-directed layout algorithm (among many others) capable of handling very large graphs.
572:
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
607:, software for visualising biological networks. The base package includes force-directed layouts as one of the built-in methods.
1155:
1125:
184:
to more central positions in the drawing; it may also affect the vertex spacing within a single component. Analogues of
197:
177:
27:
940:
884:
848:
583:
The combination of attractive forces on adjacent vertices, and repulsive forces on all vertices, was first used by
164:, without using a separate repulsive force. Minimizing the difference (usually the squared difference) between
399:
is the number of nodes of the input graph. This is because the number of iterations is estimated to be linear (
1178:
871:
648:
476:
per iteration. As a rough guide, in a few seconds one can expect to draw at most 1,000 nodes with a standard
317:
47:
647:
Grandjean, Martin (2015), "Introduction à la visualisation de données, l'analyse de réseau en histoire",
225:
66:
Force-directed graph drawing algorithms assign forces among the set of edges and the set of nodes of a
1194:
438:
216:
For forces defined from springs whose ideal length is proportional to the graph-theoretic distance,
839:
316:
approach to metric MDS can be applied to graph drawing as described above. This has been proven to
305:
169:
129:
196:, forces may also be placed on the control points of these curves, for instance to improve their
1199:
834:
210:
87:
971:
Kamada, Tomihisa; Kawai, Satoru (1989), "An algorithm for drawing general undirected graphs",
625:, software that implements most of the force-directed layout algorithms (GEM, LGL, GRIP, FMÂł).
506:
444:
346:
769:
de Leeuw, Jan (1988), "Convergence of the majorization method for multidimensional scaling",
723:
682:
479:
97:
402:
8:
742:
705:
313:
236:
232:
221:
217:
727:
686:
1161:
1107:
1022:
946:
786:
713:
672:
382:
308:(MDS) since the 1930s, and physicists also have a long history of working with related
165:
1151:
1121:
1039:
984:
936:
880:
844:
790:
708:; Trott, L. (2012), "Force-directed graph drawing using social gravity and scaling",
434:
240:
1026:
745:; Kobourov, S. G.; Trott, L. (2011), "Force-directed Lombardi-style graph drawing",
251:
The following are among the most important advantages of force-directed algorithms:
1165:
1143:
1113:
1064:
1014:
980:
928:
922:
778:
622:
569:
290:
83:
950:
1135:
1002:
577:
573:
334:
79:
71:
1068:
701:
587:; additional pioneering work on this type of force-directed layout was done by
429:
185:
75:
746:
46:
in an aesthetically-pleasing way. Their purpose is to position the nodes of a
1188:
924:
Proceedings of the 2003 ACM Symposium on
Software Visualization (SoftVis '03)
547:
273:
156:
of each spring is proportional to the graph-theoretic distance between nodes
67:
43:
31:
Visualization of links between pages on a wiki using a force-directed layout
1018:
329:
The main disadvantages of force-directed algorithms include the following:
193:
189:
94:
An alternative model considers a spring-like force for every pair of nodes
55:
23:
Social network visualization using a force-directed graph drawing algorithm
1147:
932:
1109:
1082:
1052:
867:
826:
19:
829:; Koren, Yehuda (2002), "Graph drawing by high-dimensional embedding",
782:
740:
441:-based method FADE can improve the running time to be linearithmic, or
181:
900:
604:
39:
1142:, Lecture Notes in Computer Science 2025, vol. 2025, Springer,
312:
problems - so extremely mature approaches exist. As an example, the
870:(2001), "FADE: Graph Drawing, Clustering, and Visual Abstraction",
616:
805:
718:
677:
628:
564:
Force-directed methods in graph drawing date back to the work of
168:
and ideal distances between nodes is then equivalent to a metric
228:
these differences and, hence, find a good layout for the graph.
873:
831:
309:
699:
927:, New York, NY, USA: ACM, pp. 77–86, figures on p. 212,
610:
669:
Spring
Embedders and Force-Directed Graph Drawing Algorithms
51:
motion of the edges and nodes or to minimize their energy.
920:
1118:
Graph
Drawing: Algorithms for the Visualization of Graphs
1042:
A Multilevel
Algorithm for Force-Directed Graph-Drawing
1005:(1991), "Graph Drawing by Force-Directed Placement",
509:
482:
447:
405:
385:
349:
339:
The typical force-directed algorithms are in general
132:
100:
209:
is repeated iteratively until the system comes to a
1000:
588:
1040:http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf
530:
495:
468:
420:
391:
371:
148:
118:
1179:Book chapter on Force-Directed Drawing Algorithms
1186:
861:
859:
220:gives a very well-behaved (i.e., monotonically
1133:
1057:Proceedings of the London Mathematical Society
865:
856:
503:per iteration technique, and 100,000 with a
86:are used to separate all pairs of nodes. In
970:
592:
825:
1085:(1984), "A Heuristic for Graph Drawing",
838:
717:
676:
646:
768:
666:
26:
18:
996:
994:
966:
964:
16:Physical simulation to visualize graphs
1187:
764:
762:
1081:
1051:
748:Proc. 19th Symposium on Graph Drawing
584:
565:
991:
961:
224:) and mathematically elegant way to
759:
741:Chernobelskiy, R.; Cunningham, K.;
710:Proc. 20th Int. Symp. Graph Drawing
266:drawing, and dynamic graph drawing.
13:
1140:Drawing graphs: methods and models
1101:
14:
1211:
1172:
1007:Software: Practice and Experience
589:Fruchterman & Reingold (1991)
74:-like attractive forces based on
803:
324:
1075:
1055:(1963), "How to draw a graph",
1045:
1033:
914:
650:Geschichte und Informatik 18/19
973:Information Processing Letters
893:
819:
797:
734:
693:
660:
640:
525:
519:
463:
457:
415:
409:
366:
353:
296:Strong theoretical foundations
113:
101:
1:
956:quickly "tidy up" the layout.
806:"3D Phylogenetic Tree Viewer"
667:Kobourov, Stephen G. (2012),
634:
246:
1116:; Ioannis G. Tollis (1999),
985:10.1016/0020-0190(89)90102-6
149:{\displaystyle \delta _{ij}}
36:Force-directed graph drawing
7:
1001:Fruchterman, Thomas M. J.;
901:"A Gallery of Large Graphs"
598:
10:
1216:
559:
203:
38:algorithms are a class of
771:Journal of Classification
593:Kamada & Kawai (1989)
61:
1069:10.1112/plms/s3-13.1.743
1013:(11), Wiley: 1129–1164,
777:(2), Springer: 163–180,
531:{\displaystyle n\log(n)}
469:{\displaystyle n\log(n)}
372:{\displaystyle O(n^{3})}
306:multidimensional scaling
259:other type of algorithm.
170:multidimensional scaling
1108:di Battista, Giuseppe;
126:where the ideal length
1181:by Stephen G. Kobourov
1087:Congressus Numerantium
1019:10.1002/spe.4380211102
532:
497:
470:
422:
393:
373:
343:to run in cubic time (
318:converge monotonically
293:graph-drawing systems.
211:mechanical equilibrium
150:
120:
32:
24:
1148:10.1007/3-540-44969-8
979:(1), Elsevier: 7–15,
933:10.1145/774833.774844
533:
498:
496:{\displaystyle n^{2}}
471:
439:Barnes–Hut simulation
423:
394:
374:
151:
121:
119:{\displaystyle (i,j)}
30:
22:
879:, pp. 197–210,
833:, pp. 207–219,
507:
480:
445:
421:{\displaystyle O(n)}
403:
383:
347:
255:Good-quality results
178:connected components
130:
98:
80:electrically charged
1134:Kaufmann, Michael;
1003:Reingold, Edward M.
728:2012arXiv1209.0748B
687:2012arXiv1201.3011K
437:. For example, the
314:stress majorization
237:simulated annealing
233:global optimization
218:stress majorization
82:particles based on
783:10.1007/BF01897162
700:Bannister, M. J.;
656:, pp. 109–128
568:, who showed that
528:
493:
466:
418:
389:
369:
241:genetic algorithms
198:angular resolution
146:
116:
88:equilibrium states
33:
25:
1157:978-3-540-42062-0
1127:978-0-13-301615-4
1120:, Prentice Hall,
570:polyhedral graphs
543:Poor local minima
435:N-body simulation
392:{\displaystyle n}
235:methods, include
1207:
1195:Graph algorithms
1168:
1136:Wagner, Dorothea
1130:
1114:Roberto Tamassia
1096:
1094:
1079:
1073:
1071:
1049:
1043:
1037:
1031:
1029:
998:
989:
987:
968:
959:
958:
918:
912:
911:
909:
907:
897:
891:
889:
878:
866:Quigley, Aaron;
863:
854:
853:
842:
823:
817:
816:
814:
812:
801:
795:
793:
766:
757:
755:
754:, pp. 78–90
753:
738:
732:
730:
721:
697:
691:
689:
680:
664:
658:
657:
655:
644:
578:Tutte embeddings
537:
535:
534:
529:
502:
500:
499:
494:
492:
491:
475:
473:
472:
467:
427:
425:
424:
419:
398:
396:
395:
390:
378:
376:
375:
370:
365:
364:
155:
153:
152:
147:
145:
144:
125:
123:
122:
117:
1215:
1214:
1210:
1209:
1208:
1206:
1205:
1204:
1185:
1184:
1175:
1158:
1138:, eds. (2001),
1128:
1104:
1102:Further reading
1099:
1080:
1076:
1063:(52): 743–768,
1050:
1046:
1038:
1034:
999:
992:
969:
962:
943:
919:
915:
905:
903:
899:
898:
894:
887:
876:
864:
857:
851:
824:
820:
810:
808:
802:
798:
767:
760:
751:
743:Goodrich, M. T.
739:
735:
706:Goodrich, M. T.
698:
694:
665:
661:
653:
645:
641:
637:
601:
574:convex position
562:
508:
505:
504:
487:
483:
481:
478:
477:
446:
443:
442:
404:
401:
400:
384:
381:
380:
360:
356:
348:
345:
344:
327:
249:
206:
186:magnetic fields
137:
133:
131:
128:
127:
99:
96:
95:
64:
17:
12:
11:
5:
1213:
1203:
1202:
1197:
1183:
1182:
1174:
1173:External links
1171:
1170:
1169:
1156:
1131:
1126:
1103:
1100:
1098:
1097:
1074:
1044:
1032:
990:
960:
941:
913:
892:
885:
855:
849:
840:10.1.1.20.5390
818:
796:
758:
733:
692:
659:
638:
636:
633:
632:
631:
626:
620:
614:
608:
600:
597:
561:
558:
557:
556:
544:
540:
539:
527:
524:
521:
518:
515:
512:
490:
486:
465:
462:
459:
456:
453:
450:
430:N-body problem
417:
414:
411:
408:
388:
368:
363:
359:
355:
352:
337:
326:
323:
322:
321:
297:
294:
286:
283:
280:
277:
270:
267:
263:
260:
256:
248:
245:
205:
202:
143:
140:
136:
115:
112:
109:
106:
103:
63:
60:
44:drawing graphs
15:
9:
6:
4:
3:
2:
1212:
1201:
1200:Graph drawing
1198:
1196:
1193:
1192:
1190:
1180:
1177:
1176:
1167:
1163:
1159:
1153:
1149:
1145:
1141:
1137:
1132:
1129:
1123:
1119:
1115:
1111:
1106:
1105:
1093:(11): 149–160
1092:
1088:
1084:
1078:
1070:
1066:
1062:
1058:
1054:
1048:
1041:
1036:
1028:
1024:
1020:
1016:
1012:
1008:
1004:
997:
995:
986:
982:
978:
974:
967:
965:
957:
952:
948:
944:
942:1-58113-642-0
938:
934:
930:
926:
925:
917:
902:
896:
888:
886:3-540-41554-8
882:
875:
874:
869:
862:
860:
852:
850:3-540-00158-1
846:
841:
836:
832:
828:
822:
807:
804:Vose, Aaron.
800:
792:
788:
784:
780:
776:
772:
765:
763:
750:
749:
744:
737:
729:
725:
720:
715:
711:
707:
703:
696:
688:
684:
679:
674:
670:
663:
652:
651:
643:
639:
630:
627:
624:
621:
618:
615:
612:
609:
606:
603:
602:
596:
594:
590:
586:
581:
579:
575:
571:
567:
553:
549:
548:local minimum
545:
542:
541:
522:
516:
513:
510:
488:
484:
460:
454:
451:
448:
440:
436:
431:
412:
406:
386:
361:
357:
350:
342:
338:
336:
332:
331:
330:
325:Disadvantages
319:
315:
311:
307:
302:
299:While simple
298:
295:
292:
287:
285:Interactivity
284:
281:
278:
275:
274:graph-drawing
271:
268:
264:
261:
257:
254:
253:
252:
244:
242:
238:
234:
229:
227:
223:
219:
214:
212:
201:
199:
195:
194:spline curves
191:
190:circular arcs
187:
183:
179:
173:
171:
167:
163:
159:
141:
138:
134:
110:
107:
104:
92:
89:
85:
84:Coulomb's law
81:
77:
73:
70:. Typically,
69:
68:graph drawing
59:
57:
52:
49:
45:
41:
37:
29:
21:
1139:
1117:
1090:
1086:
1083:Eades, Peter
1077:
1060:
1056:
1053:Tutte, W. T.
1047:
1035:
1010:
1006:
976:
972:
954:
923:
916:
904:. Retrieved
895:
872:
868:Eades, Peter
830:
827:Harel, David
821:
809:. Retrieved
799:
774:
770:
747:
736:
709:
702:Eppstein, D.
695:
668:
662:
649:
642:
585:Eades (1984)
582:
566:Tutte (1963)
563:
551:
340:
335:running time
328:
300:
250:
230:
215:
207:
174:
161:
157:
93:
65:
53:
35:
34:
1110:Peter Eades
433:related to
276:algorithms.
262:Flexibility
76:Hooke's law
1189:Categories
635:References
341:considered
279:Simplicity
247:Advantages
222:convergent
182:centrality
40:algorithms
835:CiteSeerX
791:122413124
719:1209.0748
678:1201.3011
605:Cytoscape
552:down-hill
517:
455:
379:), where
269:Intuitive
172:problem.
166:Euclidean
135:δ
56:planarity
1027:31468174
617:Graphviz
599:See also
226:minimize
1166:1808286
724:Bibcode
683:Bibcode
629:Prefuse
560:History
204:Methods
1164:
1154:
1124:
1025:
951:824991
949:
939:
906:22 Oct
883:
847:
837:
811:3 June
789:
310:n-body
301:ad-hoc
291:online
72:spring
62:Forces
1162:S2CID
1023:S2CID
947:S2CID
877:(PDF)
787:S2CID
752:(PDF)
714:arXiv
673:arXiv
654:(PDF)
623:Tulip
611:Gephi
333:High
48:graph
1152:ISBN
1122:ISBN
937:ISBN
908:2017
881:ISBN
845:ISBN
813:2012
239:and
160:and
42:for
1144:doi
1065:doi
1015:doi
981:doi
929:doi
779:doi
514:log
452:log
192:or
1191::
1160:,
1150:,
1112:;
1091:42
1089:,
1061:13
1059:,
1021:,
1011:21
1009:,
993:^
977:31
975:,
963:^
953:,
945:,
935:,
858:^
843:,
785:,
773:,
761:^
722:,
712:,
704:;
681:,
671:,
595:.
580:.
243:.
200:.
58:.
1146::
1095:.
1072:.
1067::
1030:.
1017::
988:.
983::
931::
910:.
890:.
815:.
794:.
781::
775:5
756:.
731:.
726::
716::
690:.
685::
675::
526:)
523:n
520:(
511:n
489:2
485:n
464:)
461:n
458:(
449:n
416:)
413:n
410:(
407:O
387:n
367:)
362:3
358:n
354:(
351:O
162:j
158:i
142:j
139:i
114:)
111:j
108:,
105:i
102:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
