Patent ID: 8543944

Claim:
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.