Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
2001-07-17
2003-02-04
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
Reexamination Certificate
active
06515666
ABSTRACT:
BACKGROUND OF INVENTION
1. Field of Invention
This invention relates to the field of graph visualization, and specifically to the field of constructing abstractions of graphs, using a computer, for the purpose of human understanding. In this context, the word graph is used in the mathematical sense, consisting of a collection of vertices joined by edges.
2. Background of the Invention
Graphs are presented to humans with the intent of conveying information. The presentation is made on a computer screen, driven by a computer, usually in an interactive environment, so that the user can control the presentation. The layout of the graph, and appearance of its elements, are chosen to portray those aspects of the graph that are thought to be of interest at the time. As the graph becomes large, clever layouts fail to be sufficient to create a picture that can be comprehended easily, and the intended information is not communicated readily, if at all.
To a small extent, this may be addressed in an interactive interface by zooming, panning, and distorting a fixed layout. In particular, fisheye views can offer some selected detail in the context of the entire graph. But these approaches, while always useful as augmentations, do not go very far towards appreciating large graphs.
A more fruitful approach is to present the human viewer with an abstraction of the graph. The abstraction is itself a graph a simplification that retains the salient features of the underlying raw graph. To be of much utility, the abstraction method must offer means of reducing the graph's complexity while still communicating the important aspects. Since the definition of important aspects varies not only with the raw graph, the project, and the human viewer, but also with the moment, the abstraction method must be versatile and rapid.
The needs for graph abstraction have been recognized for a long time, and the prior art teaches much about graph element elision and composition.
To obtain composition (grouping) of vertices, classical graphs have been augmented with an additional graph, here called a composition graph, that specifies how vertices may be grouped. The nature of this composition graph, and its interaction with the raw (classical) graph, has followed an assortment of models.
Eick and Wills (S. G. Eick and G. J. Wills, Navigating Large Networks with Hierarchies,
Proceedings of Visualization
'93, IEEE Computer Society Press, Los Alamitos, Calif., 1993, pp. 204-210) grouped vertices by defining a composition graph whose form was a forest and whose leaves were raw graph vertices. Clusters represented by internal nodes in the forest could be opened and closed to obtain abstractions. This so-called clustered graph model was used by Huang and Eades (M. L. Huang and P. Eades, A Fully Animated Interactive System for Clustering and Navigating Huge Graphs,
Graph Drawing
, 6
th
International Symposium, GD
'98, Lecture Notes In Computer Science, No. 1547, S. H. Whitesides, ed., Springer, 1998, pp. 374-383) in their disclosure of the DA-TU system in which abstractions of a clustered graph are obtained by opening and closing clusters independently, and clusters may be hidden from the drawing; in their system, clusters are arranged in local regions and outlined by boxes.
Sugiyama and Misue, 1991 (K. Sugiyama and K. Misue, Visualization of Structural Information: Automatic Drawing of Compound Digraphs,
IEEE Transactions on Systems, Man, and Cybernetics
, Vol. 21, No. 4, July/August 1991, pp. 876-892) suggested using a more general model than clustered graphs. Their compound graphs employ a composition graph that is still a tree, but whose vertices may all be raw graph vertices. In other words, edges representing both adjacency and inclusion are permitted. Each cluster may be open or closed. When a cluster is closed, its contents do not appear; when open, its contents are drawn in a convex region.
It is common practice in graph visualization programs to permit the ad hoc condensation of collections of vertices and permit hiding of vertices. Representative systems are disclosed by Kimelman et al. (D. Kimelman, B. Leban, T. Roth, and D. Zernik, Reduction of Visual Complexity in Dynamic Graphs, Graph Drawing, DIMACS International Workshop, GD '94, Lecture Notes In Computer Science, No. 894, R. Tamassia and I. G. Tollis, eds, Springer, 1995, pp. 218-225), Frolich and Werner (M. Frolich and M. Werner, Demonstration of the Interactive Graph Visualization System da Vinci, Graph Drawing, DIMACS International Workshop, GD '94, Lecture Notes In Computer Science, No. 894, R. Tamassia and I. G. Tollis, eds, Springer, 1995, pp. 266-269), Sander (G. Sander, Graph Layout Through the VCG Tool, Graph Drawing, DIMACS International Workshop, GD '94, Lecture Notes In Computer Science, No. 894, R. Tamassia and I. G. Tollis, eds, Springer, 1995, pp. 194-205), Benz (H. Benz, KGB: A Customizable Graph Browser, Graph Drawing, Symposium on Graph Drawing, GD '95, Lecture Notes In Computer Science, No. 1027, F. J. Brandenburg, ed., Springer, 1996, pp. 20-23), Sugiyama and Misue, 1996 (K. Sugiyama and K. Misue, A Generic Compound Graph Visualizer/Manipulator: D-ABDUCTOR, Graph Drawing, Symposium on Graph Drawing, GD '95, Lecture Notes In Computer Science, No. 1027, F. J. Brandenburg, ed., Springer, 1996, pp. 500-503), Huang and Eades (1998), and Carmignani et al. (A. Carmignani, G. DiBattista, W. Didimo, F. Matera, and M. Pizzonia, Visualization of the Autonomous Systems Interconnections with Hermes, Graph Drawing, 8
th
International Symposium, GD 2000, Lecture Notes In Computer Science, No. 1984, J. Marks, ed., Springer, 2001, pp. 150-163).
Herman et al. (I. Herman, G. Melan ç on, and M. S. Marshall, Graph Visualization and Navigation in Information Visualization: A Survey,
IEEE Transactions on Visualization and Computer Graphics
, Vol. 6, No. 1, January-March 2000, pp. 24-43) offer an overview of the work in graph visualization.
Despite the considerable work reported in this area, the prior art fails to address many graph abstraction needs.
To begin, many of the systems assume special structure to the raw graph, and do not consider the possibility of multiple raw graphs contributing to the abstraction. In practice, raw graphs have arbitrary structure that must be accommodated, including the possibilities that the raw graphs may contain loops and that each pair of adjacent vertices may be joined by perhaps thousands of edges, as might result by representing state transitions, transactional information, or multifaceted relationships between vertices. Rendering all of such edges in a drawing is likely to be distracting; performing analysis on such graphs may also be expensive if all edges need to be traversed repeatedly. In some cases, multiple edges between a pair of vertices should be retained, but abstractions disclosed in the prior art do not teach the handling of such a situation.
As mentioned above, it is desirable to collect groups of vertices and represent each by a composite vertex. Composite vertices can, in turn, also contain other composites. The optimum directed graph that represents this vertex composition, the composition graph, may not necessarily form a tree: raw graph vertices can be present in more than one group, as can composite vertices. Such situations would arise when describing multiple inheritance for class design, or subsystems that appear in multiple places (and perhaps multiple levels) in hardware design. In general, the graph showing the relation between composite vertices and raw graph vertices is an arbitrary directed acyclic graph. Yet no disclosure of a system employing a composition graph other than a forest is offered by the prior art, and such a generalization would not be accommodated in existing systems in an obvious way.
The prior art offers no abstraction methods in which one can surface a portion of a closed composite vertex's content, or suppress the effects of a portion of a closed composite vertex.
The removal of edges or vertices from abstractions can
Bloor Stephen M.
Luu Matthew
LandOfFree
Method for constructing graph abstractions does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for constructing graph abstractions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for constructing graph abstractions will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3160772