The Effect of the Layout Algorithms  

The following sequence of layouts shows the same graph visualized by different layout algorithms. The graph is cyclic, so the algorithm tree can't be used.

» More example graphs: Trees and similar Cyclic graphs Force-directed layout Manhattan Layout Different layouts of a graph Subgraph nesting Graphs with 100+ nodes Graphs with 100+ subgraphs Graph of the month 12 random graphs  GIF SVGPNGPSGDL

A key problem is selecting the nodes that appear at the top level of the graph. The layout algorithm looks for candidates that have no incoming edges yet at least one outgoing edge. If such nodes do not exist as in this example (Example 10), the algorithms mindegree, minindegree, maxoutdegree are the most appropriate algorithms.

The fine-tuning phase eliminates long edges, meaning the tuned graph is more compact. Note that the tuned graph created by maxdephtslow need not be of maximum depth because fine-tuning may have reduced the depth further. The tuned graph created by mindepthslow needn't be of minimum depth, either. All these partitioning algorithms are heuristics.

Example 10: A cyclic graph

graph: {
  node: {title:"A" label:"Start of all"}
  node: {title:"B"}  node: {title:"C"}  node: {title:"D"}
  node: {title:"E"}  node: {title:"F"}  node: {title:"G"}
  node: {title:"H"}  node: {title:"I"}  node: {title:"J"}
  node: {title:"K"}

  edge.thickness: 3
  edge: {source:"A" target:"B"}
  edge: {source:"A" target:"C"}
  edge: {source:"A" target:"D"}
  edge: {source:"A" target:"E"}
  edge: {source:"A" target:"F"}
  edge: {source:"A" target:"J"}
  edge: {source:"B" target:"D"}
  edge: {source:"C" target:"E"}
  edge: {source:"D" target:"F"}
  edge: {source:"F" target:"K"}
  edge: {source:"J" target:"K"}
  edge: {source:"A" target:"G"}
  edge: {source:"G" target:"H"}
  edge: {source:"H" target:"I"}
  edge: {source:"I" target:"A"}
}

Here follows a discussion of all the different hierarchical layout algorithms with and without fine-tuning for this example.

• normal, finetuning: no
  The normal layout algorithm breaks the cycle so that only one reverted edge is necessary (see top left of Figure 19).

• normal, finetuning: yes
  Compared to the previous layout, the fine-tuning phase has balanced the position of the node J. The long edge I->Start is not balanced since this would create additional reverted edges (see top right of Figure 19).

• dfs, finetuning: no
  The layout algorithms dfs, mindepth, minindegree, maxoutdegree and maxdegree happen to result in the same layout (see bottom left of Figure 19).

• dfs, finetuning: yes
  The algorithms dfs, mindepth, minindegree, maxoutdegree and maxdegree happen to result in the same layout (see bottom right of Figure 19).

• minbackward, finetuning: no
  This is almost the same layout as for the normal layout algorithm. Again only one reverted edge is necessary. The layout algorithm maxdepth without fine-tuning results in the same layout (see top left of Figure 20).

• minbackward, finetuning: yes
  Compared to the layout without fine-tuning, here the long edge I->Start is partially eliminated and the position of node J is balanced again (see top right of Figure 20).

• maxdepth, finetuning: no
  Same as minbackward without fine-tuning (see top left of Figure 20).

• maxdepth, finetuning: yes
  The long edge I->Start is now fully eliminated. Here, the fine-tuning phase is allowed to revert additional edges (see bottom left of Figure 21).

• mindepth, finetuning: no
  The layout algorithms dfs, mindepth, minindegree, maxoutdegree and maxdegree happen to result in the same layout (see bottom left of Figure 19).

• mindepth, finetuning: yes
  Compared to the previous layout the long edge I->Start is eliminated. The algorithms dfs, mindepth, minindegree, maxoutdegree and maxdegree happen to result in the same layout (see bottom right of Figure 19).

• maxdepthslow, finetuning: no
  This depth six layout is in fact of maximum depth as compared to all the other variants (see middle left of Figure 20).

• maxdepthslow, finetuning: yes
  The fine-tuning phase eliminates the long edge Start->G. Thus, the layout is no longer of maximum depth. Fine-tuning may destroy the maximum depth property (see middle right of Figure 20).

• mindepthslow, finetuning: no
  Graphs that are of minimum depth tend to have many nodes at the top level. Compared to all untuned graphs, this layout is of minimum depth. It should be noted, however, that the algorithm mindepth with fine-tuning is able to produce a flatter layout (see bottom left of Figure 20).

• mindepthslow, finetuning: yes
  Compared to the previous layout, the long edge I->Start is balanced again (see bottom right of Figure 20).

• maxindegree, finetuning: no
  Here node D is placed at the level zero because it has the maximum indegree. Node K is not chosen for level zero because it doesn't have any outgoing edges (see top left of Figure 21).

• maxindegree, finetuning: yes
  Once again the long edge I->Start of the previous algorithm is eliminated by balancing the position of node I. The algorithms dfs, mindepth and minindegree happen to result in the same layout (see top right of Figure 21).

• minindegree, finetuning: no
  The layout algorithms dfs, mindepth, minindegree, maxoutdegree and maxdegree happen to result in the same layout (see bottom left of Figure 19).

• minindegree, finetuning: yes
  The algorithms dfs, mindepth, minindegree, maxoutdegree and maxdegree happen to result in the same layout (see bottom right of Figure 19).

• maxoutdegree, finetuning: no
  The layout algorithms dfs, mindepth, minindegree, maxoutdegree and maxdegree happen to result in the same layout (see bottom left of Figure 19).

• maxoutdegree, finetuning: yes
  The algorithms dfs, mindepth, minindegree, maxoutdegree and maxdegree happen to result in the same layout (see bottom right of Figure 19).

• minoutdegree, finetuning: no
  Nodes E and K with a minimum outdegree of zero cannot be start nodes because start nodes have to have at least one successor otherwise they would create single-node components of the spanning tree. Start nodes can be any other nodes except Start, from which B, C, and G happen to be selected (see middle left of Figure 21).

• minoutdegree, finetuning: yes
  The long edges Start->B, Start->C and Start->G are eliminated (see middle right of Figure 21).

• maxdegree, finetuning: no
  The Start node has the maximum number of incoming and outgoing edges, so it is selected as the start node of the spanning tree, i.e. it appears at the topmost level. The layout algorithms dfs, mindepth, minindegree, maxoutdegree and maxdegree happen to result in the same layout (see bottom left of Figure 19).

• maxdegree, finetuning: yes
  Compared to the previous layout the long edge I->Start is eliminated. The algorithms dfs, mindepth, minindegree, maxoutdegree and maxdegree happen to result in the same layout (see bottom right of Figure 19).

• mindegree, finetuning: no
  The candidates for start nodes of the spanning tree are B, C, G, H, I and J because they have a minimum degree of two. B, C and G happen to be selected as the start nodes. Note that nodes E and K are not candidates for start nodes because they do not have outgoing edges. The layout algorithms minoutdegree and mindegree happen to result in the same layout (see middle left of Figure 21).

• mindegree, finetuning: yes
  Compared to the previous layout, the long edges Start->B Start->C and Start->G are eliminated. This changes the structure of the layout entirely (see bottom right of Figure 21).

  

Figure 19: Layout Algorithms: normal, dfs, mindepth, minindegree, maxoutdegree and maxdegree

  

Figure 20: Layout Algorithms: minbackward, maxdepth, maxdepthslow and mindepthslow

  

Figure 21: Layout Algorithms: maxindegree, minoutdegree, mindegree and maxdepth