Algorithm For Drawing Directed Acyclic Graphs
First Claim
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.
1 Assignment
0 Petitions
Accused Products
Abstract
A system and method for drawing directed acyclic graphs is disclosed. In particular, an algorithm, as implemented in a method and system, to aesthetically layout directed acyclic graphs is presented. The algorithm includes methods to reduce the number of edge crossings and increase the number of straight edges in such drawings. The algorithm keeps short and straight edges wherever possible and gives preference to vertical edges. It also provides an edge-crossing reduction heuristic to refine the layout obtained after standard median heuristic layout, and further provides a method to focus on important paths in the graph through layout.
-
Citations
24 Claims
-
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 Dependent Claims (2, 3, 4, 5, 6, 7, 8, 21)
-
-
9. A method, executable by a computer processor, for drawing directed acyclic graphs, the method comprising:
-
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 the nodes of the 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 for directed acyclic graph. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
-
17. A computer-implemented method for drawing directed acyclic graphs, the method comprising:
-
receiving information representing a directed acyclic graph; generating a layout of the directed acyclic graph, the layout 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 along x-coordinate axis to generate a compacted DAG layout; and assigning new y-coordinates to the nodes of the compacted DAG layout such that the nodes do not overlap in the y-coordinate, to generate a new layout for directed acyclic graph. - View Dependent Claims (18)
-
-
19. A method, executable by a computer processor, for focusing on interesting paths in the directed acyclic graphs through layout, the method comprising:
-
dividing interesting paths into one or more path-clusters; dividing the nodes of the interesting paths into node clusters; determining an order in which to lay out the node clusters. - View Dependent Claims (20, 22, 23, 24)
-
Specification