US 8,543,944 B2Granted

Fast edge routing for interactive diagramming

AssigneeMicrosoft Corporation

InventorsTimothy G. Dwyer, Lev Nachmanson

Life of this patent

Estimating the term…

Loading patent…

Abstract

An edge routing system is described herein that uses a spatial decomposition to achieve faster routing, and more quickly generates a sparse visibility graph using a cone spanner. The system provides two approaches that can be used separately or in combination to achieve faster—and hence more scalable and more interactive—edge routing using approximate shortest paths. The first approach uses a spatial decomposition of the nodes in a graph, moving them slightly to obtain strictly disjoint convex hulls around groups of nodes, and then computing visibility graphs over these composite hulls rather than individual nodes. The second approach generates a sparse visibility-graph spanner to accelerate the process of producing the visibility graph. The system allows high quality obstacle avoiding edge routing for large diagrams in interactive diagramming applications where very fast refreshes of routing are used with many nodes moving at the same time.

Claims17

Dependent claims

A computer-implemented method for performing fast edge routing for a graph in an interactive diagramming application, the method comprising:

receiving a layout of nodes for which the edges are to be routed to avoid the nodes;
performing spatial decomposition on the received layout of nodes to reduce a number of obstacles to consider during routing between each connected pair of nodes of the graph in the interactive diagramming application, wherein performing spatial decomposition comprises,
creating a tree that holds each of the nodes in a received graph layout;
after creating the tree, shifting nodes to eliminate overlap between node shapes, the nodes shifted no more than a threshold level of movement that places an upper bound on how far nodes can be moved;
computing one or more convex hulls based on one or more groupings of nodes in the created tree;
and
selecting convex hulls for routing between each pair of leaves in the tree, wherein spatial decomposition further comprises,
producing a visibility graph based on the reduced number of obstacles;
routing the edges of the graph in the interactive diagramming application to avoid the nodes in accordance with the produced visibility graph;
and
rendering the graph based on the layout of nodes and the determined routing of edges to display the nodes and edges to a user in a user interface of the interactive diagramming application,
wherein the preceding steps are performed by at least one processor.

9 more elements

A computer system for faster routing of edges for interactive diagramming of large numbers of nodes, the system comprising:

a processor and memory configured to execute software instructions embodied in the following components;
a layout input component configured to receive a layout for which to plan the routing of edges for connected nodes in a graph;
a tree building component configured to build a tree data structure that describes one or more relationships of nodes in the received layout;
a hull building component configured to group nodes so that construction of a visibility graph can consider groups instead of individual nodes to yield fewer obstacles and faster processing;
a node shift component configured to shift nodes in the graph to remove overlaps between groups generated by the hull building component, wherein a shift threshold is selected to allow for easier routing without significantly changing the visual appearance of the graph, wherein the shift threshold is a threshold level of movement that places an upper bound on how far a node can be moved;
a visibility graph component configured to produce a visibility graph over the remaining nodes and groups of nodes using cone spanning to produce a sparse visibility graph;
and
a routing output component configured to provide the resulting visibility graph to a renderer for displaying visual output of the routing process to a user of an interactive diagramming application.

5 more elements

Dependencies are inferred from the claim text.