Graph drawing

Graph drawing is the area of mathematics and computer science concerned with turning a graph, a set of vertices joined by edges, into a two-dimensional or sometimes three-dimensional picture that people can read. It draws on geometric graph theory and information visualization, and it serves uses such as social network analysis, cartography, linguistics and bioinformatics. A drawing is a pictorial representation and must not be confused with the graph itself, because very different layouts can depict the same graph: in the abstract only the pairing of vertices by edges matters, while in a concrete drawing the placement of vertices and edges affects how understandable, usable and attractive it is. Quality is judged by measures such as the number of edge crossings, the area of the drawing, symmetry, the number of bends in edges, edge lengths, angular resolution and slope number. The main layout families are force-based, spectral, orthogonal, tree, layered (Sugiyama style), arc diagram, circular and dominance drawing, and named procedures include the Reingold-Tilford algorithm for drawing trees and Tamassia's algorithm for minimizing bends in orthogonal drawings of planar graphs. Dynamic graph drawing adds the goal of preserving the viewer's mental map while edges are added and deleted over time.