Techniques for drawing curved edges in graphs

• US 8,730,241 B2
• Filed: 09/08/2008
• Issued: 05/20/2014
• Est. Priority Date: 09/08/2008
• Status: Active Grant

• Current Assignee: Fair Isaac Corporation
• Original Assignee: Fair Isaac Corporation
• Inventors: Chhaparwal, Gaurav, Doshi, Navin, Kolipaka, Kashyap Babu Rao
• Primary Examiner(s): Thompson, James A
• Assistant Examiner(s): Hoang, Peter
• Application Number:
  US12/206,687
• Publication Number:
  US 20100060642A1
• Time in Patent Office: 2,080 Days
• Field of Search: 345440-443
• US Class Current: 345/440
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

A system and method for drawing curved edges in graphs is disclosed. The system and method implement a heuristic algorithm to draw curved edges in graphs using Bezier curves. The algorithm assumes that every pair of nodes has a unique edge between them. It also assumes that the graph is “leveled,” which means the nodes can be grouped such that all the nodes in a group are laid out at the same y location in a vertical layout. Any generic graph can be converted to a leveled graph, so the techniques described in the algorithm are applicable to any graph.

Claims

1. A method comprising:

receiving, by at least one processor, fixed positions of a plurality of nodes of a graph, the plurality of nodes and the fixed positions being always unadjustable so as to maintain compactness of the graph;

determining, by at least one processor, two or more curves to connect corresponding pairs of nodes of the plurality of nodes;

selecting, by at least one processor and based on a cost function and from the two or more curves, optimal curves for the corresponding pairs of nodes, the cost function for each curve being based at least on a distance of a farthest point on a curve from a straight line joining end points of the curve, the end points of the curve being positions of nodes to be connected by the curve; and

connecting, by at least one processor when a possible connecting of the corresponding pairs of nodes via respective straight lines results in more edge crossings than possible edge crossings associated with the optimal curves, the plurality of nodes by using the corresponding optimal curves, two or more connected nodes being connected to at least two other corresponding nodes.

2. The method of claim 1, wherein:

the two or more curves are determined for each pair of nodes of the plurality of nodes;

an optimal curve of the optimal curves is selected for each corresponding pair of nodes;

each pair of nodes is connected by a corresponding optimal curve of the optimal curves; and

each connected node of the two or more connected nodes is connected to at least two other nodes.

3. The method of claim 1, wherein the cost function is evaluated after the nodes become unadjustable.

4. The method of claim 1, wherein the nodes maintain orientation with respect to other nodes after the nodes are adjusted once and until the connecting is performed by the optimal curves so as to maintain the compactness of the graph.

5. The method of claim 1, further comprising:

rendering, by at least one processor, the connected plurality of nodes and the corresponding optimal curves in an output device.

6. The method of claim 1, wherein the optimal curves are associated with a maximum acceptable value of the cost function.

7. The method of claim 1, wherein at least one of the optimal curves is a cubic curve.

8. The method of claim 1, wherein at least one of the optimal curves is a quadratic curve.

12. The method of claim 1, wherein the unadjustable fixed positions of the nodes are located in a plurality of levels such that the connected plurality of nodes are arranged in the plurality of levels, the connected plurality of nodes displaying data specifying corresponding ranges for values of a plurality of health parameters, two or more health parameters being associated with a plurality of corresponding nodes at each corresponding level.

13. The method of claim 12, wherein the plurality of health parameter comprise glucose, body mass index, age, insulin, pedigree, pregnancies, blood pressure, and triceps.

9. A non-transitory computer program product storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:

receiving fixed positions of a plurality of nodes of a graph, the plurality of nodes and the fixed positions being unadjustable after being fixed once so as to maintain compactness of the graph;

determining two or more curves to connect corresponding pairs of nodes of the plurality of nodes;

selecting, based on a cost function and from the two or more curves, optimal curves for the corresponding pairs of nodes, the cost function for each curve being based at least on a distance of a farthest point on a curve from a straight line joining end points of the curve, the end points of the curve being positions of nodes to be connected by the curve; and

connecting the plurality of nodes by using the corresponding optimal curves when a connecting of the corresponding pairs of nodes via respective optimal curves results in less intersections of the corresponding optimal curves than intersections of respective straight lines if the corresponding pairs of nodes were to be connected via the respective straight lines instead of the corresponding optimal curves, two or more connected nodes being connected to at least two other corresponding nodes.

10. The computer program product of claim 9, wherein the cost function is evaluated after the nodes become unadjustable.

11. The computer program product of claim 9, wherein the nodes maintain orientation with respect to other nodes after the nodes are adjusted once and until the connecting is performed by the optimal curves so as to maintain the compactness of the graph.

14. The computer program product of claim 9, wherein the connected plurality of nodes are arranged in different levels associated with respective health parameters comprising data associated with one or more of:

glucose, body mass index, age, insulin, pedigree, pregnancies, blood pressure, and triceps.