Graph Layout

Graph layout is concerned with placing a set of vertices and edges in the drawing in such a way that the reader of a graph can easily identify and understand the contents of the graph. When trying to place the vertices and edges of the graph, current graph layout methods aim to place the parts of the graph according to various aesthetic criteria to improve readability. A layout is a ``good'' layout if the layout achieves a majority of the aesthetic criteria. These aesthetics have been determined by research into the cognitive efforts of the human mind. Work by Ware et al. in [1] have tried to collate some important aesthetic criteria with Gestalt^2.1 principles when laying out a graph. These include:

• Minimal edge crossings
• Minimal edge bends
• Preservation of symmetry
• Nodes should be evenly distributed.
• Long edges should be avoided.
• Nodes shouldn't overlap each other in the layout.

When dealing with digraphs, additional aesthetic criteria for graph layout can be expected of the layout algorithm. One criterion for layout of digraphs is that the algorithm should preserve the hierarchical nature of the graph by having all the directed edges point towards one particular side of the drawing, the default traditionally being down. However layout algorithms that are designed for use with digraphs typically need the removal of cycles. If we have a node $u$ that has a directed edge to node $v$ and $v$ in turn has a directed edge back to $u$ , the algorithm can not determine which node should be placed above the other in the resulting drawing. Work by Bastert et al. in [17] and Eades et al. in [18] provide an algorithm that approximates the maximum acyclic subgraph of some graph $G$ in linear time.

Figure: A graph that is symmetrical (), and the same graph with minimised edge crossings (). Reproduced from [25]

[] []

The aesthetic criteria mentioned are applied to a layout based upon various characteristics of a graph such as symmetry, hierarchical placement, etc. However there has not yet been one algorithm that has determined a set of aesthetics for graphs in all application domains. For example, a user may want a layout that preserves the symmetrical nature of a graph as shown in Fig. , however an algorithm that is more concerned with minimising the number of edge crossings may layout the graph like that in Fig. . The graph in Fig.  does not make the symmetry obvious to the reader, contrary to the wishes of the user. This is where the non-interactivity of graph layout algorithms can seriously detract from the quality and presentation of a final layout, and ultimately from what the users wants.

Trying to achieve all these aesthetic criteria is considered difficult as more often than not the algorithm will have to break one criterion in order to achieve another. Various algorithms have been devised, and integrated into static layout tools, to calculate the best position of the vertices, and the routing of the edges in order to produce a readable graph, with attempts to achieve the aforementioned aesthetic goals. Some of the more popular approaches will be briefly examined next.