Routing edges with ordered bundles

Abstract

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.