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.