title: Best Graph Drawing Algorithm For Hierarchical Data?
body: <p>I have a collection of directed <em>acyclic</em> graphs that are <em>nearly</em> trees, in the following sense: each graph has a <em>root</em>, and the vertices are organized into <em>levels</em> such that if <em>v</em><sub>1</sub> and <em>v</em><sub>2</sub> are vertices, then if the level of <em>v</em><sub>1</sub> is less than the level of <em>v</em><sub>2</sub>, then there is no edge from <em>v</em><sub>2</sub> to <em>v</em><sub>1</sub> in the graph, although there may be many edges from <em>v</em><sub>1</sub> to vertices at the same or a greater level. For example, an expression tree, a function call graph, or a linear class hierarchy, would be examples of such graphs. Here is an example of such a graph:</p>
  
  <pre><code>              A1            
               /  \           A1 -&gt; A4, A3
              /    \          A3 -&gt; A2, A6, A7
            A4  A2--A3        A2 -&gt; A6
                | \ / \
                A6 \_ A7
  </code></pre>
  
  <p>There are a plethora of graph-drawing algorithms, and I can't determine which is optimal for this situation. Some preliminary research indicates that algorithms for drawing Hasse diagrams might be appropriate, but it seems that the output of such algorithms isn't geared toward the type of data structures that I'm trying to model. There are also several algorithms for modeling hierarchical data, but I'm not sure which would balance ease of implementation with efficiency. One problem with the former approach is that these graphs have a root, as well as a direction. If possible, the algorithm would support <em>cyclic</em> graphs, and minimize the number of numeric computations, but this isn't necessary. For these reasons, I would prefer to avoid force-directed algorithms, and if possible, the GraphViz algorithms such as <em>dot</em>.</p>