Optimizing edge crossing computations when creating a drawing of a directed graph having a minimum number of edge crossings

摘要

A candidate graph crossing point counter can be initialized. Level pairs can be sorted in descending order according to a number of connections between the level pairs. Evaluation of the candidate graph can progress according to the order of the level pairs so that those pairs likely to have the greatest number of connections are processed first. While the candidate graph crossing point counter is at an intermediate value and before a crossing point total is calculated for the candidate graph, it can be determined that the intermediate value is at least as great as a crossing point total of a best current graph for the directional graph. Calculation of the candidate graph crossing point total can be halted at the intermediate value. The candidate graph can be discarded from a possibility of being a minimized graph during a determination of a graph drawing for the directional graph.

主权项

1. A method for optimizing a directional graph computation comprising:
initializing, at a computing device, a candidate graph crossing point counter, wherein the candidate graph is an acyclic, layered graph representation of a directional graph, wherein the layered graph comprises a plurality of level pairs, and wherein a sum of the set of crossing point totals per level pair for the plurality of level pairs equals the crossing point total for the layered graph; while the candidate graph crossing point counter is at an intermediate value and before the crossing point total is calculated for the candidate graph, determining, at the computing device, that the intermediate value is at least as great as a crossing point total of a best current graph for the directional graph; and responsive to the determination, halting calculation, at the computing device, of the candidate graph crossing point total at the intermediate value and discarding the candidate graph from a possibility of being a graph having a minimized number of crossings during a determination of a graph drawing for the directional graph, where the graph drawing is a heuristic approximation of a graph drawing for the directional graph having a minimized number of edge crossings.