Graph drawing
Graphss are often represented pictorially as follows: draw a dot for every vertex, and for every edge draw an arc connecting its endpoints. If the graph is directed, indicate the endpoint of an edge by an arrow.There are different approaches to graph layout and these are considered under a branch of graph theory termed as graph drawing.
Note that this graphical representation (a layout) 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). All that matters is which vertices are connected to which others by how many edges.
Some of the well known layouts are
- spring layout - by using an energy function that is minimized so that nodes and edges spread out by 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.
External links
Here are some examples of graph layouts:
- http://www.aisee.com/gallery
- http://www.research.att.com/sw/tools/graphviz/examples/
- http://www.tomsawyer.com/gallery/gallery.html
Popular graph layout tools
- http://www.research.att.com/sw/tools/graphviz/
- http://www.cs.uni-sb.de/RW/users/sander/html/gsvcg1.html
- http://www.aisee.com
- http://www.tulip-software.org
- http://www.oreas.com/
- http://www.ilog.com
- http://www.algorithmic-solutions.com/enalgocomskomm.htm
- http://jgraph.sourceforge.net/features.html
- http://www.yworks.com/en/products.htm
- ftp://ftp.cs.uni-sb.de/pub/graphics/vcg/doc/tr-A03-94.ps.gz