System and method for visualizing massive multi-digraphs

• US 20020154175A1
• Filed: 01/04/2001
• Published: 10/24/2002
• Est. Priority Date: 01/04/2001
• Status: Active Grant

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Korn, Jeffrey, Abello, James
• Granted Patent: US 6,781,599 B2
• Time in Patent Office: Days
• US Class Current: 715/853
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

In accordance with a feature of the invention, a hierarchy of multi-digraph layers may be constructed on top of an input multi-digraph. Each layer represents a multi-digraph obtained from an equivalence relation defined on the edge set of the input multi-digraph. In accordance with a further feature of the invention, each subgraph is small enough to be represented visually in a variety of novel ways.

Claims

1. A method of processing an input multi-digraph comprising:

constructing a hierarchy of multi-digraph layers on top of the multi-diagraph;

extracting a graph slice from the hierarchy; and

creating a visual representation of the graph slice.

2. The invention of claim 1 wherein each layer represents a multi-digraph obtained from an equivalence relation defined on edges of the input multi-digraph.

3. The invention of claim 2 wherein each layer has edges representing an equivalence class of edges at a previous layer.

4. The invention of claim 1 further comprising the steps of:

receiving input from a user;

replacing the graph slice with a second graph slice extracted from the hierarchy; and

creating a visual representation of the second graph slice.

5. The invention of claim 1 wherein the input multi-digraph is larger than main memory.

6. A system for visualizing an input multi-digraph comprising:

a computational engine enabled to construct a hierarchy of multi-digraph layers on top of the multi-diagraph and to extract graph slices from the hierarchy; and

a graphical engine in communication with the computational engine and enabled to create visual representations of the graph slices.

7. The invention of claim 6 wherein each layer represents a multi-digraph obtained from an equivalence relation defined on edges of the input multi-digraph.

8. The invention of claim 7 wherein each layer has edges representing an equivalence class of edges at a previous layer.

9. The invention of claim 6 wherein the graphical engine requests graph slices from the computational engine in response to navigational commands from a user.

10. The invention of claim 6 wherein the computational engine and the graphical engine communicate across a communication network.

11. The invention of claim 6 wherein the input multi-digraph is larger than main memory.

13. The invention of claim 12 wherein each matrix element is represented as a needle in a grid.

14. The invention of claim 12 wherein each matrix element is represented as a segment of circular histogram rooted at a point.

15. The invention of claim 14 wherein each point is shown in an associated geographic location on a map.

16. The invention of claim 14 wherein each point is placed on top of each other along an axis.

17. The invention of claim 12 wherein each matrix element is represented as a tick placed at the end of a segment drawn around a single point.

18. The invention of claim 12 wherein the matrix elements are aggregated in the visual representation.

12. A method of visualizing a graph slice of a multi-digraph hierarchy comprising:

arranging edges of the graph slice in a matrix representation;

creating a visual representation of each matrix element of the matrix representation.