Force-directed graph layout

Abstract

A computer implemented method for generating a force-directed layout for a graph is provided together with computer systems and programs for carrying out the method. The graph includes a plurality of vertices and the layout is dependent on a force exerted by each vertex on every other vertex. The method generates an initial layout of the plurality of vertices. The method determines an effect of global interactions based on the force between vertices by: grouping vertices based on their location in the initial layout; and determining an aggregate effect of each group of vertices as a whole. The method determines, for each vertex, an effect of local interactions based on the force with the vertices located in a region of the initial layout proximate to the vertex. The method determines an adjustment to the location of each vertex based, at least in part, on the combined effects of the global and local interactions on that vertex and applies the determined adjustment to each vertex.

Dependencies are inferred from the claim text.