Graph drawing

From Exampleproblems

Jump to: navigation, search

As a branch of Graph theory, Graph drawing applies topology and geometry to derive visual and haptic representations of graphs. It identifies classes of graphs, such that for each class there exists an effective procedure for embedding any of its members into some metric space. It then sets out to formally specify, implement, and verify such procedures.

Graph drawing is motivated by applications that require visualization, navigation, fabrication, or beauty of its physical or conceptual artifacts that have been embedded into a graph's structure. It is a key ingredient in technologies as varied as VLSI circuit design, social networks, user interface design, software engineering, computer networks, e-commerce, cartography, and bioinformatics.

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.

Based on these concepts and caveats, there had emerged different graph layouts. Here are some of the better known ones:

  • force-based layout - by using an energy function that is minimized so that nodes and edges spread out by attraction and repulsion.
  • 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 (ie 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.



Contents

See also

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

Examples of graph layouts:

A collection of animated interactive graph layouts:

a wiki for keeping track of the open problems in the field of graph drawing]

Popular graph layout tools

Retrieved from "http://www.exampleproblems.com/wiki/index.php/Graph_drawing"
Argan Oil
Natural Skin Care
Organic Skin Care
visitor stats