Applying numerical approximation to general graph drawing

Abstract

A simple approach to graph layout is fast and results in graphs that lend themselves to full visualization on a standard-sized computer monitor. The algorithm implemented allows the use the same spring and repulsion energies as in the force-directed model, or any other reasonably behaved energy function. In addition, numerical methods, either the technique of polynomial approximation or quadratic approximation, are applied. This allows approximating the minimum or maximum of a general function by picking a small set of points and computing the local optima of a polynomial function that passes through them. Polynomial or quadratic approximation is used to produce candidate drawings and, ultimately, to select a low-energy drawing from these candidates.

Having thus described our invention, what we claim as new and desire to secure by Letters Patent is as follows: 
     
       1. A computer-implemented method of drawing a graph, comprising steps of: gathering information about the graph including a node set and an edge set;   generating a set of candidate drawings based upon said node set and edge set of said graph, wherein for at least one candidate drawing within said set of candidate drawings a second set of drawings is generated,   at least one new drawing is generated based upon polynomial approximation associated with said second set of drawings, and   upon determining that said new drawing satisfies a predetermined criterion, said new drawing is added to said set of candidate drawings;     selecting at least one candidate drawing within said set of candidate drawings; and   outputting the selected candidate drawing for generating a visual representation of said graph.   
     
     
       2. The method of claim 1, wherein said second set of drawings is generated by perturbing said at least one candidate drawing. 
     
     
       3. The method of claim 1, wherein said second set of drawings is generated by combining drawings with said set of candidate drawings. 
     
     
       4. The method of claim 1, wherein, upon determining that said new drawing satisfies a predetermined criterion said at least one candidate drawing is replaced by said new drawing in said set of candidate drawings. 
     
     
       5. The method of claim 1, wherein the generating step comprises the following steps applied to each candidate drawing within said set of candidate drawings: for a given candidate drawing,   perturbing said given candidate drawing to generate a second set of drawings corresponding to said given candidate drawing;   generating a new drawing based upon a polygonal approximation associated with said second set of drawings corresponding to said given candidate drawing; and   upon determining that said new drawing satisfies a predetermined criterion, replacing said given candidate drawing with said new drawing in said set of candidate drawings.   
     
     
       6. The method of claim 1, wherein the generating step comprises the following steps applied to a subset of said set of candidate drawings: combining a subset of candidate drawings to generate a second set of drawings;   generating a new drawing based upon a polygonal approximation associated with said second set of drawings;   upon determining that said new drawing satisfies a predetermined criterion, including said new drawing in said set of candidate drawings.   
     
     
       7. The method of claim 6, further comprising the step of: upon determining that said new drawing satisfies a predetermined criterion, removing said subset of candidate drawings from the set of candidate drawings.   
     
     
       8. The method of claim 1, wherein said polynomial approximation is performed in accordance with steps which include: choosing a univariate function which maps a parameter thereof to a domain of drawings of said graph; and   determining a point of said univariate function which maps to an optimal drawing by (i) determining which ones of said second set of drawings have a best evaluation with respect to an evaluation function defined over said domain of drawings and (ii) returning as said set of candidate drawings said ones of said second set of drawings having said best evaluation.   
     
     
       9. The method of claim 8, further comprising: perturbing at least one of said set of candidate drawings by choosing said univariate function to produce drawings such that points of said univariate function correspond to a continuum of change from a given drawing.   
     
     
       10. The method of claim 9, wherein said second set of drawings is generated by combining drawings within said set of candidate drawings, said combining being perform by choosing said univariate function to parameterize a combination of the drawings such that the points of said univariate function correspond to a continuum of combinations. 
     
     
       11. The method of claim 10, wherein said continuum of combinations includes a convex combination of two drawings. 
     
     
       12. The method of claim 8, wherein said generating step includes: using a force-directed model to determine a resultant force vector on a single node of said node set;   generating a set of drawings by moving said single node in a direction of said resultant force vector in a predetermined manner;   evaluating each of said set of drawings to determine, based on said model, energy contributed by said single node; and   using said polynomial approximation to generate said at least one new drawing based on said evaluating step.   
     
     
       13. The method of claim 12, wherein said force-directed model is based on one of Hooke's law and Coulomb's law. 
     
     
       14. The method of claim 12, wherein said polynomial approximation is a quadratic approximation used to determine a parabola passing through three predetermined points determined based on said force-directed model, and wherein a candidate is generated as one corresponding to a minimum of said parabola. 
     
     
       15. The method of claim 8, wherein said predetermined criterion corresponds to an indication of whether said univariate function is found as a result of said quadratic approximation step. 
     
     
       16. The computer implemented method of graph drawing of claim 1, wherein said step of generating candidate graph drawings includes generating at least one candidate graph drawing by moving at least two of said nodes simultaneously.