As a branch of graph theory, Graph drawing applies topology and geometry to derive two- and three-dimensional representations of graphs. Graph drawing is motivated by applications such as VLSI circuit design, social network analysis, cartography, and bioinformatics. A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ... A Möbius strip, an object with only one surface and one edge; such shapes are an object of study in topology. ... For other uses, see Geometry (disambiguation). ... It has been suggested that VHSIC be merged into this article or section. ... Not to be confused with social network services such as MySpace, etc. ... Cartography or mapmaking (in Greek chartis = map and graphein = write) is the study and practice of making maps or globes. ... Map of the human X chromosome (from the NCBI website). ...

Methods

Graphs are usually represented pictorially using dots to represent vertices, and arcs to represent the edges between connected vertices. Arrows can be used to show the orientation of directed edges. Note that this graphical representation (a graph layout or an embedding) should not be confused with the graph itself (the abstract, non-graphical structure). Very different layouts can correspond to the same graph (see external link #1). In the abstract, all that matters is which vertices are connected to which others by how many edges. In the concrete, however, the arrangement of these vertices and edges impacts understandability, usability, fabrication cost, and aesthetics. Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ... An arrow is a graphical symbol like →, ←, used to point or indicate direction, being in its simplest form a line segment with a triangle affixed to one end, and in more complex forms a representation of an actual arrow. ... The torus is an orientable surface. ... The Parthenons facade showing an interpretation of golden rectangles in its proportions. ...

Based on these concepts and caveats, there are different graph layout strategies, such as:

• force-based layout: gradient-descent minimization of an energy function based on physical metaphors related to molecular mechanics.
• spectral layout: layout using as coordinates the eigenvectors of a matrix such as the Laplacian derived from the adjacency matrix of the graph.
• orthogonal layout: layout with edges running horizontally or vertically, with approaches that reduce the number of edge crossovers and area covered. These are of great interest in the areas of VLSI and PCB layout design
• symmetric layout: these attempt to find symmetry groups within the graph
• tree layout: these show a rooted tree-like formation, suitable for trees (i.e., graphs without cycles)
• hierarchical layouts: these attempt to find a source and sink within a directed graph and arrange the nodes in layers with most edges starting from the source and flowing in the direction of the sink

In some applications of graph drawing it is important to formally specify, implement, and verify such procedures. Force-directed algorithms are a class of algorithms for drawing graphs in an aesthetically pleasing way. ... The term molecular mechanics refers to the use of Newtonian mechanics to model molecular systems. ... In linear algebra, the eigenvectors (from the German eigen meaning own) of a linear operator are non-zero vectors which, when operated on by the operator, result in a scalar multiple of themselves. ... In mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries), which may be numbers or, more generally, any abstract quantities that can be added and multiplied. ... In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. ... In mathematics and computer science, the adjacency matrix of a finite directed or undirected graph G on n vertices is the n × n matrix where the nondiagonal entry is the number of edges from vertex i to vertex j, and the diagonal entry is either twice the number of loops... VLSI may refer to: Very-large-scale integration, a process for the creation of electronic integrated circuits VLSI Technology (1979–1999), a former American integrated circuit manufacturer, now a part of Philips Electronics VLSI Solution, a Finnish integrated circuit manufacturer Category: ... Part of a 1983 Sinclair ZX Spectrum computer board. ... The symmetry group of an object (e. ... A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. ... A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ... A program specification is the definition of what a computer program is expected to do. ... “Programming” redirects here. ... In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics. ...

Metrics

K₄ (the complete graph with 4 vertices) can be drawn with or without overlapping edges (move one of the corners to the outside)

There is no "best" layout — different ways of displaying a graph emphasize different characteristics. One measure of a graph drawing algorithm's quality is the number of edge crossings it draws. While some graphs cannot be drawn without edge crossings, some graphs can. These are called planar graphs. According to this metric, "good" algorithms draw graphs with as few edge crossings as possible. Image File history File links Complete_graph_K4. ... Image File history File links Complete_graph_K4. ... In the mathematical field of graph theory, a complete graph is a simple graph where an edge connects every pair of distinct vertices. ... For the Talib Kweli album Quality (album) Quality can refer to a. ... In graph theory, a planar graph is a graph that can be drawn so that no edges intersect (or that can be embedded) in the plane. ...

Another possible measure is the closeness of vertices, many graphs look better if non-adjacent vertices are not plotted close to each other. A further measure is the nearness of a vertex to a non-adjacent edge, this distance needs to be sufficiently big for an aesthetically pleasing appearance.

See also

• Hasse diagram, a type of graph drawing specialized to partial orders
• State diagrams, graphical representations of finite state machines
• Graphviz, a widely used open-source graph drawing system from AT&T
• Routing (EDA)

In the mathematical discipline known as order theory, a Hasse diagram (pronounced HAHS uh, named after Helmut Hasse (1898–1979)) is a simple picture of a finite partially ordered set, forming a drawing of the transitive reduction of the partial order. ... In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... State diagrams are used to graphically represent finite state machines. ... Fig. ... Visual rendering by Graphviz. ... This article is about the current AT&T. For the 1885-2005 company, see American Telephone & Telegraph. ... Routing is a crucial step in the design of integrated circuits. ...

References

• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.
• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Algorithms for Drawing Graphs: an Annotated Bibliography. Computational Geometry: Theory and Applications 4:235-282 (1994). http://www.cs.brown.edu/people/rt/gd.html
• Isabel F. Cruz, Roberto Tamassia. Graph Drawing Tutorial. http://www.cs.brown.edu/people/rt/gd.html

External links

The following graph drawing web sites are particularly notable:

• graphdrawing.org, the official web site of the Graph Drawing Steering Committee, organizers of the annual International Symposium on Graph Drawing. Includes a description of the graphml graph description language, example graph data, and links to many other graph drawing resources.
• The Graph drawing e-print archive, including information on papers from all Graph Drawing symposia.

See Graph drawing at the Open Directory Project for many additional links related to graph drawing. The Open Directory Project (ODP), also known as dmoz (from , its original domain name), is a multilingual open content directory of World Wide Web links owned by Netscape that is constructed and maintained by a community of volunteer editors. ...

• [1], web site of Chisio; an academic, open-source, easy to use graph visualization tool