most recent 30 from http://mathoverflow.net 2013-05-18T19:24:40Z http://mathoverflow.net/feeds/question/5253 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/5253/algorithms-for-laying-out-directed-graphs Brent Hagany 2009-11-12T20:39:18Z 2010-07-07T01:33:33Z

<p>I have an acyclic digraph that I would like to draw in a pleasing way, but I am having trouble finding a suitable algorithm that fits my special case. My problem is that I want to fix the x-coordinate of each vertex (with some vertices having the same x-coordinate), and only vary the y. My aesthetic criteria are (in order of importance):</p> <ol> <li>Ensure no two vertices are too close together</li> <li>Minimize edge crossings and near misses</li> <li>Make a reasonable use of the entire drawing space</li> </ol> <p>I have tried several (modified) force-directed algorithms, but they haven't met my expectations on at least one of these - usually too many edge crossings.</p> <p>Has anyone come across a problem like this, or can you point me to some good papers that deal with restrictions like this?</p>

http://mathoverflow.net/questions/5253/algorithms-for-laying-out-directed-graphs/5261#5261 David Eppstein 2009-11-12T21:45:41Z 2009-11-12T21:45:41Z

<p>If the x-coordinates are compatible with the acyclic structure of your DAG (that is, for an edge u->v, the x coordinate of u should always be less than that of v) then this is a standard problem in graph drawing, known as Sugiyama-style layered drawing. (Usually it is the y coordinates that are fixed but that makes no difference.) Some versions of the problem (e.g. finding the exact minimum number of edge crossings) can be NP-hard but effective heuristics are known. See e.g. chapter 9 of Di Battista, Tamassia, and Eades, "Graph Drawing: Algorithms for the Visualization of Graphs", Prentice-Hall, 1999.</p> <p>Searching Google scholar for "layered graph drawing" should also turn up some more recent references, but be careful that some of them (including mine) which use the term to mean something unrelated.</p>

http://mathoverflow.net/questions/5253/algorithms-for-laying-out-directed-graphs/5278#5278 Jay Kominek 2009-11-12T23:10:31Z 2009-11-12T23:10:31Z

<p>The <a href="http://www.graphviz.org/Documentation.php" rel="nofollow">documentation for GraphViz</a> (a software package that does this sort of thing) has a number of papers on the subject included.</p>