title: Computing depth of each node in a "maximally packed" DAG
body: <p><em>(Note: I thought about asking this on <a href="https://cstheory.stackexchange.com/">https://cstheory.stackexchange.com/</a>, but decided my question is not theoretical enough -- it's about an algorithm.  If there is a better Stack Exchange community for this post, I'm happy to listen!)</em></p>
  
  <p>I'm using the terminology "starting node" to mean a node with no links into it, and "terminal node" to mean a node with no links out of it.  So the following graph has starting nodes A and B and terminal nodes F and G:</p>
  
  <p><a href="https://i.stack.imgur.com/Bc65d.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Bc65d.png" alt="image of a Directed Acyclic Graph"></a></p>
  
  <p>I want to draw it with the following rules:</p>
  
  <ul>
  <li>at least one starting node has a depth of 0.</li>
  <li>links always point from top to bottom</li>
  <li>nodes are packed vertically as closely as possible</li>
  </ul>
  
  <p>Using those rules, depth of for each node is shown for the graph above.  Can someone suggest an algorithm to compute the depth of each node that runs in less than O(n^2) time?</p>
  
  <h3>update:</h3>
  
  <p>I tweaked the graph to show that the DAG may contain starting and terminal nodes at different depths.  (This was a case that I didn't consider in my original buggy answer.)  I also switched terminology from "x coordinate" to "depth" in order to emphasize that this is about "graphing" and not "graphics".</p>