Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1997-09-18
2004-08-10
Shah, Sanjiv (Department: 2176)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S215000
Reexamination Certificate
active
06774899
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a computerized system for drawing graphs. More particularly, it relates to an interactive, constraint-based graph-drawing system.
BACKGROUND OF THE INVENTION
Most small graphs, such as those that appear in publications or presentations, are drawn with the aid of primitive commercial drawing tools, like PowerPoint from MicroSoft or Claris Draw. These drawing tools do not make it easy to introduce and maintain the exquisite symmetries, spacings and alignments that graphic designers typically utilize in their work. Typically, these tools merely allow the placement of nodes on a screen and connection lines between the nodes. The user can interactively move the nodes about on the screen in order to improve the visual appearance of the graph. Often, the user may also apply simple constraints to organize the nodes on the screen. For example, the user can select a set of nodes which are then aligned horizontally or vertically. However, the graph-drawing algorithms only apply the constraint once; if the user subsequently changes a node, the system does not automatically realign the nodes.
Other, more complicated systems use layout algorithms in order to set certain constraints or goals for the layout of a graph. These constraints or goals allow portions of the graph to be set automatically. Generally, graph-layout algorithms minimize specific fixed properties in order to improve the readability and esthetic appearance of graphs. Such properties include maximization of display symmetry, minimizing edge crossings or edge bends, limiting edge lengths to be more uniform, and uniformly distributing nodes. However, minimization of these properties can be an extremely difficult computational problem. Thus, laying out graphs with such systems can be extremely long and tedious. Furthermore, even when the properties are easily minimized, an acceptable graph is not necessarily obtained. Primarily, this is because automated layouts do not consider what the user deems to be important. No specific layout structure is relevant to all types of graphs. Thus, the best layout depends upon the user's purpose for the graph, not universally relevant geometric properties of a display. In this regard, user input is extremely important.
Tyson R. Henry and Scott E. Hudson disclose a system in “Interactive Graph Layout”,
Proceedings of the ACM Symposium on User Interface Software and Technology
, page 55 (November, 1991) for composing graph layouts which provide some automation of layout as well as user control. As disclosed in this article, the user interacts with the system to designate a hierarchy of layout algorithms. However, this system is intended for large graphs and is extremely complicated. It requires an understanding of the hierarchical relationship in setting algorithms. Although constraints have permanence, the final layout is not intuitively obvious from the constraints themselves. Since contraints are hierarchically arranged, the effects of some constraints will be modified or cancelled by the application of other constraints. Particularly, the permissible constraints appear to maximize certain distances to create uniformity in the graph. Sometimes for readability, the user would like disuniformity in a graph in order to emphasize certain areas.
Ed Dengler, Mark Friedell and Joe Marks, in “Constraint-Driven Diagram Layout”,
Proceedings of the
1993
IEEE Symposium on Visual Languages
, pp 330-335 (August, 1993) disclose a system for using constraints in diagram layouts. This system is based upon the use of visual organization features (VOFs). VOFs are specific arrangements of related nodes in the diagram. The system in this article does not describe or presume where the VOFS come from. Rather, it is merely a system for producing a layout result based upon the nodes, edges and VOFS. The layout is optimized using a hybrid process of simulation and stochastic search in order to meet the constraints. Also, the spring constraints are applied in the incremental process in a specified order. The order is determined by the extent of restrictiveness of a constraint. This tries to prevent the incremental improvement approach from being trapped at local optimums. Also, in the Dengler et al. approach, an initial layout is randomly selected. In order to provide improved performance, several different random initial locations can be used. The optimums obtained from each of the initial locations are compared to determine a global optimum in meeting the constraints.
SUMMARY OF THE INVENTION
The deficiencies of known systems for drawing small graphs exquisitely are substantially overcome by the present invention which relates to an interactive system for drawing graphs using constraints. In this system, constraints, nodes and edges are added or deleted from a displayed graph by the user through an interface. With each change, the system redetermines dynamically the position of the nodes and edges based upon the constraints. A generalized spring algorithm is used to enforce the constraints and provide locally optimum placement of the nodes with respect to all constraints. Furthermore, the present invention includes a small set of macro constraints which can be applied to the graph. These constraints are specifically designed for a graph drawing. They are “macro” in that they relate to complex relationships between nodes such as symmetry rather than simple geometric or topological relationships, such as tangency or connectedness relationships between specified points on nodes.
REFERENCES:
patent: 5193183 (1993-03-01), Bachman
patent: 5276789 (1994-01-01), Besaw et al.
patent: 5278951 (1994-01-01), Camacho et al.
patent: 5287439 (1994-02-01), Koga et al.
patent: 5381343 (1995-01-01), Bamji et al.
patent: 5450535 (1995-09-01), North
patent: 5450540 (1995-09-01), Spohrer et al.
patent: 5452238 (1995-09-01), Kramer et al.
patent: 5745122 (1998-04-01), Gay et al.
patent: 5764239 (1998-06-01), Misue et al.
patent: 5786820 (1998-07-01), Robertson
patent: 5815154 (1998-09-01), Hirschtick et al.
patent: WO 98/29820 (1998-07-01), None
Henry, T.R. and Hudson, S.E., “Interactive Graph Layout”, Proc. on the Association of Computing Machinery Symposium on User Interface Software, New York: ACM, pp. 55-64, Nov. 1991.*
Tonouchi, Toshio et al., “Creating Visual Objects by Direct Manipulation”, Proc. of the 1992 Institute of Electrical and Electronics Engineers Workshop on Visual Languages, pp. 95-101. Los Alamitos: IEEE Comp. Soc. Press, pp. 95-101, Sep. 1992.*
Dangler, Ed. et al., “Constraint-Driven Diagram Layout”, Proc. Institute of Electrical and Electronics Engineers Symposium on Visual Languages, Los Alamitos: IEEE Comp. Soc. Press, pp. 330-335, Aug. 1993.*
Kosak, Corey et al., “Automating the Layout of Network Diagrams with Specified Visual Organization”, Institute of Electrical and Electronics Engineers Trans. on Systems, Man, and Cybernetics, vol. 24, No. 3, pp. 440-454, Mar. 1994.*
Galindo, Diana et al., “Perceptually-Based Representation of Network Diagrams”, Proc. of the 4th International Conference on Document Analysis and Recognition, v. 1, Los Alamitos: IEEE Comp. Soc. Press, pp. 352-356, Aug. 1997.
Marks Joseph
Ryall Kathy
Shieber Stuart Merrill
Brinkman Dirk
Mitsubishi Electric Research Laboratories Inc.
Shah Sanjiv
LandOfFree
Drawing graphs using user selectable visual oragnization... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Drawing graphs using user selectable visual oragnization..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Drawing graphs using user selectable visual oragnization... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3353757