×

Algorithm For Drawing Directed Acyclic Graphs

  • US 20100060643A1
  • Filed: 09/08/2008
  • Published: 03/11/2010
  • Est. Priority Date: 09/08/2008
  • Status: Active Grant
First Claim
Patent Images

1. A computer-implemented method for drawing directed acyclic graphs, the method comprising:

  • receiving, in a computing system, information representing a directed acyclic graph, a computer processor of the computing system configured for;

    generating a layout of the directed acyclic graph, the layout comprised of one or more subgraphs, each subgraph comprising two or more nodes and edges that connect pairs of nodes, the nodes and edges being defined in x- and y-coordinates;

    reducing the number of edge crossings in the layout of the directed acyclic graph;

    straightening the edges of the layout of the directed acyclic graph;

    compacting one or more subgraphs along x-coordinate axis to generate a compacted DAG layout; and

    assigning new y-coordinates to the nodes of the one or more subgraphs such that the nodes do not overlap in the y-coordinate to generate a new layout of directed acyclic graph.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×