Optimizing edge crossing computations when creating a drawing of a directed graph having a minimum number of edge crossings
US8994730B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Sep 25, 2008 |
| Grant date | Mar 31, 2015 |
| Priority date | — |
| Expiry date | Oct 22, 2033 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06T17/00
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.