Editing Graph drawing (section)

==Layout methods==
[[File:Social Network Analysis Visualization.png|thumb|right|A force-based network visualization.{{sfnp|Grandjean|2014}}]]
[[File:Spectral graph drawing of small world graph.svg|thumb|Spectral graph layout visualization.]]
There are many different graph layout strategies:
*In [[force-based layout]] systems, the graph drawing software modifies an initial vertex placement by continuously moving the vertices according to a system of forces based on physical metaphors related to systems of [[spring (device)|springs]] or [[molecular mechanics]]. Typically, these systems combine attractive forces between adjacent vertices with repulsive forces between all pairs of vertices, in order to seek a layout in which edge lengths are small while vertices are well-separated. These systems may perform [[gradient descent]] based minimization of an [[energy function]], or they may translate the forces directly into velocities or accelerations for the moving vertices.<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, Section 2.7, "The Force-Directed Approach", pp. 29–30, and Chapter 10, "Force-Directed Methods", pp. 303–326.</ref>
*[[Spectral layout]] methods use as coordinates the [[eigenvector]]s of a [[Matrix (mathematics)|matrix]] such as the [[Discrete Laplace operator|Laplacian]] derived from the [[adjacency matrix]] of the graph.<ref>{{harvtxt|Beckman|1994}}; {{harvtxt|Koren|2005}}.</ref>
*Orthogonal layout methods, which allow the edges of the graph to run horizontally or vertically, parallel to the coordinate axes of the layout. These methods were originally designed for [[VLSI]] and [[Printed circuit board|PCB]] layout problems but they have also been adapted for graph drawing. They typically involve a multiphase approach in which an input graph is planarized by replacing crossing points by vertices, a topological embedding of the planarized graph is found, edge orientations are chosen to minimize bends, vertices are placed consistently with these orientations, and finally a layout compaction stage reduces the area of the drawing.<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, Chapter 5, "Flow and Orthogonal Drawings", pp. 137–170; {{harvtxt|Eiglsperger|Fekete|Klau|2001}}.</ref>
*Tree layout algorithms these show a rooted [[tree structure|tree]]-like formation, suitable for [[tree (graph theory)|trees]]. Often, in a technique called "balloon layout", the children of each node in the tree are drawn on a circle surrounding the node, with the radii of these circles diminishing at lower levels in the tree so that these circles do not overlap.<ref>{{harvtxt|Herman|Melançon|Marshall|2000}}, Section 2.2, "Traditional Layout – An Overview".</ref>
*[[Layered graph drawing]] methods (often called Sugiyama-style drawing) are best suited for [[directed acyclic graph]]s or graphs that are nearly acyclic, such as the graphs of dependencies between modules or functions in a software system. In these methods, the nodes of the graph are arranged into horizontal layers using methods such as the [[Coffman–Graham algorithm]], in such a way that most edges go downwards from one layer to the next; after this step, the nodes within each layer are arranged in order to minimize crossings.<ref>{{harvtxt|Sugiyama|Tagawa|Toda|1981}}; {{harvtxt|Bastert|Matuszewski|2001}}; {{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, Chapter 9, "Layered Drawings of Digraphs", pp. 265–302.</ref>
[[File:Goldner-Harary-linear.svg|thumb|Arc diagram]]
*[[Arc diagram]]s, a layout style dating back to the 1960s,<ref>{{harvtxt|Saaty|1964}}.</ref> place vertices on a line; edges may be drawn as semicircles above or below the line, or as smooth curves linked together from multiple semicircles.
*[[Circular layout]] methods place the vertices of the graph on a circle, choosing carefully the ordering of the vertices around the circle to reduce crossings and place adjacent vertices close to each other. Edges may be drawn either as chords of the circle or as arcs inside or outside of the circle. In some cases, multiple circles may be used.<ref>{{harvtxt|Doğrusöz|Madden|Madden|1997}}.</ref>
*[[Dominance drawing]] places vertices in such a way that one vertex is upwards, rightwards, or both of another if and only if it is [[reachability|reachable]] from the other vertex. In this way, the layout style makes the reachability relation of the graph visually apparent.<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, Section 4.7, "Dominance Drawings", pp. 112–127.</ref>