Microsoft Technology Licensing, LLC

Sergey Pupyrev

Lev Boris Nachmanson

Alexander E Holroyd

Sergey Bereg

A graph processing module is described for producing a processed graph in three phases. In a bundling phase, the graph processing module selects edges that are used to constitute paths to produce a bundled graph. In an ordering phase, the graph processing module orders paths within the bundled graph to produce an ordered bundled graph. In a separating phase, the graph processing module separates paths in the ordered bundled graph. Among other features, the graph processing module performs the selecting operation by minimizing a cost function; this has the effect of promoting bundling in the bundled graph while discouraging the presence of overly long edges in the bundled graph. The graph processing module can perform the ordering operation by selecting the ordering of paths passing through each edge based on a consideration of ordering constraints within a common subpath associated with the edge.

Routing edges with ordered bundles

A graph processing module is described for producing a visualization of a layered graph. The graph processing module operates by: bundling edges in the layered graph to produce respective edge bundles; ordering the edges associated with the edge bundles to reduce edge crossings; straightening the edges; and separating the edges in the edges bundles with respect to each other. The graph processing module can operate on a layered graph produced by the Sugiyama algorithm or some other technique, reducing clutter in the layered graph and thus improving a user's understanding of the layered graph.

Growing community of inventors

Ekaterinburg, Russia

Sergey Pupyrev