Browse Prior Art Database

Scalable Node Splash using Map based Visibility Graph Disclosure Number: IPCOM000218989D
Publication Date: 2012-Jun-14
Document File: 7 page(s) / 126K

Publishing Venue

The Prior Art Database


Disclosed is a technique for managing node position. This technique is complimentary to the visibility graph used for obstruction avoidance. It allows users to find neighboring nodes and edges in a HashMap access time (best/typical case O(1), worst case O(n)). Using this algorithm pushes neighboring nodes in a scalable way as well as allows the visibility graph for obstruction avoidance to be volatile and work on a small sub-set of the entire diagram.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 23% of the total text.

Page 01 of 7

Scalable Node Splash using Map based Visibility Graph

A common problem in diagramming domains is the layout esthetics and placement of the nodes and edges participating in the graph . The placement of nodes and edges can be an arduous and time-consuming process. Each node needs to be placed individually and then other nodes adjusted accordingly . Auto-layout algorithms can be used to address this problem, often with good results However, auto-layout can interfere with the creative thought process , as after each layout the user has to realign with the changes that have taken place, because the nodes and edges will likely be completely repositioned.

Good usability can be summarized as achieving a goal with minimal effort through an intuitive interface. Manual layout in diagramming usually does not meet this requirement, as it takes many steps to achieve the goal and often it is not clear how to perform the individual steps. For example, the following UML class diagram has a simple class inheritance hierarchy . (Figure 1)

Figure 1: Simple Class Inheritance Hierarchy

If the user wants to add a new super class to ConcreteClass 1, they must perform the following steps:

1. Add a new class to the diagram surface "SuperClass1"

2. Reorient generalization from ConcreteClass 1 to SuperClass1

3. Draw a generalization from SuperClass1 to AbstractClass

4. Observe that the layout is not in a desirable state

5. To improve this, the user must now move AbstractClass up and then adjust SuperClass1 to be equi-distant between AbstractClass and ConcreteClass1

The process entails five distinct actions to get to the desired state . In addition, them more complex cases require more steps (e.g., if there were additional relationships between ConcreteClass1 and AbstractClass).

A number of known solutions can be applied to improve this usability , but they bring another set of problems with them. For instance, it is possible to do auto-layout whenever a new shape or edge is added. This would ensure the diagram always looks decent after a node or edge addition . It may reduce the number of steps, but it would increase the time taken to complete the task since the user would have to search for


Page 02 of 7

their node or edge after each addition . Also, auto-layout can do a good job but it may not be the layout result that that the user had in mind . In large diagrams, this would be a performance concern as well since typically all the nodes in the graph would be adjusted.

Alternatively, it is easy to imagine a simple algorithm that forces a proximity radius between nodes such that if a user moves one node toward another, with-in a specific proximity, it will push the neighboring nodes away from it . The pseudo code to do this is as follows:

Example 1: Pseudo code for Pushing Proximity Nodes

for each child in diagram {

if child intersects with node {

    PushChildFromNode(child, node); }


This is an O(n) operation such that every time a user move...