Drawing Directed Acyclic Graphs: Minimizing edge crossing?

Question

Laying out the verticies in a DAG in a tree form (i.e. verticies with no in-edges on top, verticies dependent only on those on the next level, etc.) is rather simple without graph drawing algorithms such as Efficient Sugiyama. However, is there a simple algorithm to do this that minimizes edge crossing? (For some graphs, it may be impossible to completely eliminate edge crossing.) A picture says a thousand words, so is there an algorithm that would suggest something without crossing edges. (compared to this).

EDIT: The result

I've accepted Senthil's suggesting graphviz/dot -- a quick look at the docs confirms that it's very easy to use it as a library or external tool, and the output format is surprisingly easy to parse. However, I ended up choosing to use GraphSharp instead since I'm already using .NET, etc (though it's definitely not as powerful as dot). The result is "good enough", and could be made a lot better with a little edge routing and tweaking (the blurry text is because of 3.5 WPF).

Here's the complete C# code (this is all the code that references either QuickGraph or GraphSharp -- yeah; it was that easy):

internal static class LayoutManager
{
    private const string ALGORITHM_NAME = "EfficientSugiyama";
    private const bool MINIMIZE_EDGE_LENGTH = true;
    private const double VERTEX_DISTANCE = 25;
    private const double LAYER_DISTANCE = 25;
    private const double MIN_CANVAS_OFFSET = 20;

    public static void doLayout(GraphCanvas canvas)
    {
        // TODO use a background thread
        // TODO add comments
        canvas.IsEnabled = false;
        canvas.Cursor = Cursors.Wait;
        var graph = new BidirectionalGraph<GraphNode, LayoutEdge>();
        var positions = new Dictionary<GraphNode, Point>();
        var sizes = new Dictionary<GraphNode, Size>();
        foreach(var node in canvas.nodes)
        {
            var size = node.RenderSize;
            graph.AddVertex(node);
            positions.Add(node, new Point(node.left + size.Width / 2, node.top + size.Height / 2));
            sizes.Add(node, size);
        }
        foreach(var edge in canvas.edges)
        {
            graph.AddEdge(new LayoutEdge(edge));
        }

        var context = new LayoutContext<GraphNode, LayoutEdge, BidirectionalGraph<GraphNode, LayoutEdge>>(graph, positions, sizes, LayoutMode.Simple);
        var parameters = new EfficientSugiyamaLayoutParameters();
        parameters.VertexDistance = VERTEX_DISTANCE;
        parameters.MinimizeEdgeLength = MINIMIZE_EDGE_LENGTH;
        parameters.LayerDistance = LAYER_DISTANCE;
        var factory = new StandardLayoutAlgorithmFactory<GraphNode, LayoutEdge, BidirectionalGraph<GraphNode, LayoutEdge>>();
        var algorithm = factory.CreateAlgorithm(ALGORITHM_NAME, context, parameters);
        algorithm.Compute();
        canvas.deselectAll();

        var minx = algorithm.VertexPositions.Select(kvp => kvp.Value.X - (kvp.Key.RenderSize.Width / 2)).Aggregate(Math.Min);
        var miny = algorithm.VertexPositions.Select(kvp => kvp.Value.Y - (kvp.Key.RenderSize.Height / 2)).Aggregate(Math.Min);
        minx -= MIN_CANVAS_OFFSET;
        miny -= MIN_CANVAS_OFFSET;
        minx = minx < 0 ? -minx : 0;
        miny = miny < 0 ? -miny : 0;
        foreach(var kvp in algorithm.VertexPositions)
        {
            var node = kvp.Key;
            var pos = kvp.Value;
            node.left = (pos.X - (node.RenderSize.Width / 2)) + minx;
            node.top = (pos.Y - (node.RenderSize.Height / 2)) + miny;
        }
        canvas.Cursor = Cursors.Arrow;
        canvas.IsEnabled = true;
    }

    private sealed class LayoutEdge : IEdge<GraphNode>
    {
        private readonly ConnectingEdge _edge;
        public LayoutEdge(ConnectingEdge edge) { _edge = edge; }
        public GraphNode Source { get { return _edge.output.node; } }
        public GraphNode Target { get { return _edge.input.node; } }
    }

Answer 1

You could try using Topological Sorting. In a first step you can determine the levels (top to bottom) of the layout by performing a topological sort and always grouping independent nodes in a single layer. This will always succeed for directed acyclic graphs.

Then you could maybe try to perform a topological sort of each layer (left to right) taking the location of the input and output ports and probably adjacent layers into account. My image of this step is bit blurry but I can imagine that it is doable for graphs like your example.

Answer 2

Dot seems like it would fit the bill:

dot - ``hierarchical'' or layered drawings of directed graphs. The layout algorithm aims edges in the same direction (top to bottom, or left to right) and then attempts to avoid edge crossings and reduce edge length.

https://docs.google.com/viewer?url=http://www.graphviz.org/pdf/dotguide.pdf

Answer 3

A simple approach to implement crossing reduction for layered DAGs is to use the node's DFS number as the sorting key for nodes that belong to the same layer. This should produce no crossings for true trees, and descent results for DAGs that are almost trees.

For a commercial WPF component that provides hierarchical layout, see yFiles WPF. To try out the crossing reduction performance of that component you could use yEd Graph Editor [www.yworks.com/yed] or the yFiles Silverlight Graph Editor [www.yworks.com/yfilessilverlight].