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

A computer program product for optimizing a directional graph computation comprising a computer readable storage medium having computer usable program code embodied therewith, the computer usable program code comprising:

• computer usable program code configured to initialize 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;
• computer usable program code configured to determine, while the candidate graph crossing point counter is at an intermediate value and before the crossing point total is calculated for the candidate graph, that the intermediate value is at least as great as a crossing point total of a best current graph for the directional graph;
• and
• computer usable program code configured to, responsive to the determination, halt calculation 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.