HOME

TheInfoList



OR:

Graph drawing is an area of
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
and
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
combining methods from
geometric graph theory Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geomet ...
and
information visualization Data and information visualization (data viz/vis or info viz/vis) is the practice of designing and creating Graphics, graphic or visual Representation (arts), representations of a large amount of complex quantitative and qualitative data and i ...
to derive two-dimensional depictions of
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...
s arising from applications such as
social network analysis Social network analysis (SNA) is the process of investigating social structures through the use of networks and graph theory. It characterizes networked structures in terms of ''nodes'' (individual actors, people, or things within the network) ...
,
cartography Cartography (; from , 'papyrus, sheet of paper, map'; and , 'write') is the study and practice of making and using maps. Combining science, aesthetics and technique, cartography builds on the premise that reality (or an imagined reality) can ...
,
linguistics Linguistics is the scientific study of language. The areas of linguistic analysis are syntax (rules governing the structure of sentences), semantics (meaning), Morphology (linguistics), morphology (structure of words), phonetics (speech sounds ...
, and
bioinformatics Bioinformatics () is an interdisciplinary field of science that develops methods and Bioinformatics software, software tools for understanding biological data, especially when the data sets are large and complex. Bioinformatics uses biology, ...
. A drawing of a graph or network diagram is a pictorial representation of the vertices and edges of a graph. This drawing should not be confused with the graph itself: very different layouts can correspond to the same graph., p. 6. In the abstract, all that matters is which pairs of vertices are connected by edges. In the concrete, however, the arrangement of these vertices and edges within a drawing affects its understandability, usability, fabrication cost, and
aesthetics Aesthetics (also spelled esthetics) is the branch of philosophy concerned with the nature of beauty and taste (sociology), taste, which in a broad sense incorporates the philosophy of art.Slater, B. H.Aesthetics ''Internet Encyclopedia of Ph ...
. The problem gets worse if the graph changes over time by adding and deleting edges (dynamic graph drawing) and the goal is to preserve the user's mental map.


Graphical conventions

Graphs are frequently drawn as node–link diagrams in which the vertices are represented as disks, boxes, or textual labels and the edges are represented as
line segment In geometry, a line segment is a part of a line (mathematics), straight line that is bounded by two distinct endpoints (its extreme points), and contains every Point (geometry), point on the line that is between its endpoints. It is a special c ...
s, polylines, or curves in the
Euclidean plane In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...
., p. viii. Node–link diagrams can be traced back to the 14th-16th century works of Pseudo-Lull which were published under the name of
Ramon Llull Ramon Llull (; ; – 1316), sometimes anglicized as ''Raymond Lully'', was a philosopher, theologian, poet, missionary, Christian apologist and former knight from the Kingdom of Majorca. He invented a philosophical system known as the ''Art ...
, a 13th century polymath. Pseudo-Lull drew diagrams of this type for
complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
s in order to analyze all pairwise combinations among sets of metaphysical concepts. In the case of directed graphs,
arrowheads An arrowhead or point is the usually sharpened and hardened tip of an arrow, which contributes a majority of the projectile mass and is responsible for impacting and penetrating a target, or sometimes for special purposes such as signaling. ...
form a commonly used graphical convention to show their orientation; however, user studies have shown that other conventions such as tapering provide this information more effectively.
Upward planar drawing In graph drawing, an upward planar drawing of a directed acyclic graph is an Graph embedding, embedding of the graph into the Euclidean plane, in which the edges are represented as planar graph, non-crossing Monotonic function, monotonic upwards ...
uses the convention that every edge is oriented from a lower vertex to a higher vertex, making arrowheads unnecessary. Alternative conventions to node–link diagrams include adjacency representations such as circle packings, in which vertices are represented by disjoint regions in the plane and edges are represented by adjacencies between regions; intersection representations in which vertices are represented by non-disjoint geometric objects and edges are represented by their intersections; visibility representations in which vertices are represented by regions in the plane and edges are represented by regions that have an unobstructed line of sight to each other; confluent drawings, in which edges are represented as smooth curves within mathematical train tracks; fabrics, in which nodes are represented as horizontal lines and edges as vertical lines;. and visualizations of the
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...
of the graph.


Quality measures

Many different quality measures have been defined for graph drawings, in an attempt to find objective means of evaluating their aesthetics and usability. In addition to guiding the choice between different layout methods for the same graph, some layout methods attempt to directly optimize these measures. *The crossing number of a drawing is the number of pairs of edges that cross each other. If the graph is planar, then it is often convenient to draw it without any edge intersections; that is, in this case, a graph drawing represents a
graph embedding In topological graph theory, an embedding (also spelled imbedding) of a graph G on a surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs (homeomorphic images of ,1/math>) ...
. However, nonplanar graphs frequently arise in applications, so graph drawing algorithms must generally allow for edge crossings. *The
area Area is the measure of a region's size on a surface. The area of a plane region or ''plane area'' refers to the area of a shape or planar lamina, while '' surface area'' refers to the area of an open surface or the boundary of a three-di ...
of a drawing is the size of its smallest bounding box, relative to the closest distance between any two vertices. Drawings with smaller area are generally preferable to those with larger area, because they allow the features of the drawing to be shown at greater size and therefore more legibly. The
aspect ratio The aspect ratio of a geometry, geometric shape is the ratio of its sizes in different dimensions. For example, the aspect ratio of a rectangle is the ratio of its longer side to its shorter side—the ratio of width to height, when the rectangl ...
of the bounding box may also be important. *Symmetry display is the problem of finding
symmetry group In group theory, the symmetry group of a geometric object is the group of all transformations under which the object is invariant, endowed with the group operation of composition. Such a transformation is an invertible mapping of the amb ...
s within a given graph, and finding a drawing that displays as much of the symmetry as possible. Some layout methods automatically lead to symmetric drawings; alternatively, some drawing methods start by finding symmetries in the input graph and using them to construct a drawing. *It is important that edges have shapes that are as simple as possible, to make it easier for the eye to follow them. In polyline drawings, the complexity of an edge may be measured by its number of bends, and many methods aim to provide drawings with few total bends or few bends per edge. Similarly for spline curves the complexity of an edge may be measured by the number of control points on the edge. *Several commonly used quality measures concern lengths of edges: it is generally desirable to minimize the total length of the edges as well as the maximum length of any edge. Additionally, it may be preferable for the lengths of edges to be uniform rather than highly varied. *
Angular resolution Angular resolution describes the ability of any image-forming device such as an Optical telescope, optical or radio telescope, a microscope, a camera, or an Human eye, eye, to distinguish small details of an object, thereby making it a major det ...
is a measure of the sharpest angles in a graph drawing. If a graph has vertices with high degree then it necessarily will have small angular resolution, but the angular resolution can be bounded below by a function of the degree. *The slope number of a graph is the minimum number of distinct edge slopes needed in a drawing with straight line segment edges (allowing crossings). Cubic graphs have slope number at most four, but graphs of degree five may have unbounded slope number; it remains open whether the slope number of degree-4 graphs is bounded.


Layout methods

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 springs or
molecular mechanics Molecular mechanics uses classical mechanics to model molecular systems. The Born–Oppenheimer approximation is assumed valid and the potential energy of all systems is calculated as a function of the nuclear coordinates using Force field (chemi ...
. 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 Gradient descent is a method for unconstrained mathematical optimization. It is a first-order iterative algorithm for minimizing a differentiable multivariate function. The idea is to take repeated steps in the opposite direction of the gradi ...
based minimization of an energy function, or they may translate the forces directly into velocities or accelerations for the moving vertices. * Spectral layout methods use as coordinates the
eigenvector In linear algebra, an eigenvector ( ) or characteristic vector is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by ...
s of a
matrix Matrix (: matrices or matrixes) or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the m ...
such as the
Laplacian In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols \nabla\cdot\nabla, \nabla^2 (where \nabla is th ...
derived from the
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...
of the graph. *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 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. *Tree layout algorithms these show a rooted
tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...
-like formation, suitable for
trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only p ...
. 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. * Layered graph drawing methods (often called Sugiyama-style drawing) are best suited for
directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ...
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. * Arc diagrams, a layout style dating back to the 1960s, 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. * Dominance drawing places vertices in such a way that one vertex is upwards, rightwards, or both of another if and only if it is reachable from the other vertex. In this way, the layout style makes the reachability relation of the graph visually apparent.


Application-specific graph drawings

Graphs and graph drawings arising in other areas of application include * Sociograms, drawings of a
social network A social network is a social structure consisting of a set of social actors (such as individuals or organizations), networks of Dyad (sociology), dyadic ties, and other Social relation, social interactions between actors. The social network per ...
, as often offered by
social network analysis software Social network analysis (SNA) software is software which facilitates quantitative analysis of behavior, quantitative or qualitative research, qualitative social network analysis, analysis of social networks, by describing features of a network eit ...
*
Hasse diagram In order theory, a Hasse diagram (; ) is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set (S,\le) one represents each ...
s, a type of graph drawing specialized to
partial order In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements needs to be comparable ...
s *
Dessin d'enfant In mathematics, a dessin d'enfant is a type of graph embedding used to study Riemann surfaces and to provide combinatorial Invariant (mathematics), invariants for the action of the absolute Galois group of the rational numbers. The name of these e ...
s, a type of graph drawing used in
algebraic geometry Algebraic geometry is a branch of mathematics which uses abstract algebraic techniques, mainly from commutative algebra, to solve geometry, geometrical problems. Classically, it studies zero of a function, zeros of multivariate polynomials; th ...
*
State diagram A state diagram is used in computer science and related fields to describe the behavior of systems. State diagrams require that the system is composed of a finite number of states. Sometimes, this is indeed the case, while at other times this i ...
s, graphical representations of
finite-state machine A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
s * Computer network diagrams, depictions of the nodes and connections in a
computer network A computer network is a collection of communicating computers and other devices, such as printers and smart phones. In order to communicate, the computers and devices must be connected by wired media like copper cables, optical fibers, or b ...
*
Flowchart A flowchart is a type of diagram that represents a workflow or process. A flowchart can also be defined as a diagrammatic representation of an algorithm, a step-by-step approach to solving a task. The flowchart shows the steps as boxes of v ...
s and drakon-charts, drawings in which the nodes represent the steps of an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
and the edges represent
control flow In computer science, control flow (or flow of control) is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an '' ...
between steps. *
Project network A project network diagram, also known an activity network diagram (AND) is a information graphics, graph that displays the order in which a project’s activities are to be completed. Derived from the work breakdown structure, the Work breakdown ...
, graphical depiction of the chronological order in which activities of a
project A project is a type of assignment, typically involving research or design, that is carefully planned to achieve a specific objective. An alternative view sees a project managerially as a sequence of events: a "set of interrelated tasks to be ...
are to be completed. * Data-flow diagrams, drawings in which the nodes represent the components of an
information system An information system (IS) is a formal, sociotechnical, organizational system designed to collect, process, Information Processing and Management, store, and information distribution, distribute information. From a sociotechnical perspective, info ...
and the edges represent the movement of information from one component to another. *
Bioinformatics Bioinformatics () is an interdisciplinary field of science that develops methods and Bioinformatics software, software tools for understanding biological data, especially when the data sets are large and complex. Bioinformatics uses biology, ...
including
phylogenetic tree A phylogenetic tree or phylogeny is a graphical representation which shows the evolutionary history between a set of species or taxa during a specific time.Felsenstein J. (2004). ''Inferring Phylogenies'' Sinauer Associates: Sunderland, MA. In ...
s,
protein–protein interaction Protein–protein interactions (PPIs) are physical contacts of high specificity established between two or more protein molecules as a result of biochemical events steered by interactions that include electrostatic forces, hydrogen bonding and t ...
networks, and
metabolic pathway In biochemistry, a metabolic pathway is a linked series of chemical reactions occurring within a cell (biology), cell. The reactants, products, and Metabolic intermediate, intermediates of an enzymatic reaction are known as metabolites, which are ...
s. In addition, the placement and
routing Routing is the process of selecting a path for traffic in a Network theory, network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched ...
steps of
electronic design automation Electronic design automation (EDA), also referred to as electronic computer-aided design (ECAD), is a category of software tools for designing Electronics, electronic systems such as integrated circuits and printed circuit boards. The tools wo ...
(EDA) are similar in many ways to graph drawing, as is the problem of greedy embedding in
distributed computing Distributed computing is a field of computer science that studies distributed systems, defined as computer systems whose inter-communicating components are located on different networked computers. The components of a distributed system commu ...
, and the graph drawing literature includes several results borrowed from the EDA literature. However, these problems also differ in several important ways: for instance, in EDA, area minimization and signal length are more important than aesthetics, and the routing problem in EDA may have more than two terminals per net while the analogous problem in graph drawing generally only involves pairs of vertices for each edge.


Software

Software, systems, and providers of systems for drawing graphs include: * BioFabric open-source software for visualizing large networks by drawing nodes as horizontal lines. *
Cytoscape Cytoscape is an Open-source software, open source bioinformatics software platform for Visualization (graphic), visualizing Metabolic network modelling, molecular interaction networks and integrating with gene expression profiles and other state da ...
, open-source software for visualizing molecular interaction networks * Gephi, open-source network analysis and visualization software * graph-tool, a free/libre Python library for analysis of graphs *
Graphviz Graphviz (short for ''Graph Visualization Software'') is a package of open-source software, open-source tools initiated by AT&T Labs, AT&T Labs Research for Graph drawing, drawing graph (discrete mathematics), graphs (as in Vertex (graph theory ...
, an open-source graph drawing system from
AT&T Corporation AT&T Corporation, an abbreviation for its former name, the American Telephone and Telegraph Company, was an American telecommunications company that provided voice, video, data, and Internet telecommunications and professional services to busi ...
* Linkurious, a commercial network analysis and visualization software for
graph databases A graph database (GDB) is a database that uses graph structures for semantic queries with nodes, edges, and properties to represent and store data. A key concept of the system is the graph (or edge or relationship). The graph relates the data ...
*
Mathematica Wolfram (previously known as Mathematica and Wolfram Mathematica) is a software system with built-in libraries for several areas of technical computing that allows machine learning, statistics, symbolic computation, data manipulation, network ...
, a general-purpose computation tool that includes 2D and 3D graph visualization and graph analysis tools. * Microsoft Automatic Graph Layout, open-source .NET library (formerly called GLEE) for laying out graphs * NetworkX is a Python library for studying graphs and networks. *
Tulip Tulips are spring-blooming perennial herbaceous bulbiferous geophytes in the ''Tulipa'' genus. Their flowers are usually large, showy, and brightly coloured, generally red, orange, pink, yellow, or white. They often have a different colour ...
, an open-source data visualization tool * yEd, a graph editor with graph layout functionality * PGF/TikZ 3.0 with the graphdrawing package (requires
LuaTeX LuaTeX is a TeX-based computer typesetting system which started as a version of pdfTeX with a Lua (programming language), Lua scripting engine embedded. After some experiments it was adopted by the TeX Live distribution as a successor to pdfTeX (i ...
).; see also the olde
GD 2012 presentation
* LaNet-vi, an open-source large network visualization software


See also

* International Symposium on Graph Drawing *
List of Unified Modeling Language tools This article compares UML tools. UML tools are software applications which support some functions of the Unified Modeling Language. General Features See also * List of requirements engineering tools References External links


References


Footnotes


General references

*. *. *.


Specialized subtopics

*. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. * .


Further reading

*. *. *.


External links


GraphX library for .NET
: open-source WPF library for graph calculation and visualization. Supports many layout and edge routing algorithms.
Graph drawing e-print archive
including information on papers from all Graph Drawing symposia. {{Graph representations