Current Layout Efforts in Interactive Diagram Editors

Two of the most popular interactive diagramming editors are Microsoft's Visio, and The Omni Group's Omnigraffle. These tools use modifications of the Sugiyama heuristic for creating a layered layout, or a non-constraint force-directed layout algorithm to attempt to assist the user in laying out graphs. However the graphs are constantly being edited, and modified as the user interacts with the graph. It is the unknown nature of the graph that is hard to integrate these algorithms into existing tools.

Figure: Comparison of a diagram drawn in both Graphviz and Visio.

Consider the two images in Fig . The one on the left is drawn with Graphviz, the other is the same graph copied into and laid out with an inbuilt layout function in Visio. The one drawn in Visio is full of edge crossings and not laid out very well, compared to the static image drawn in Graphviz. Ware et al. in [1] puts forward the idea that one of the factors that impact on the reader's mental map is the number of edge crossings. Compared with the Graphviz image, the layout of the graph drawn in Visio has seriously deteriorated from the user's mental map. The layout has essentially resulted in a bad drawing, meaning the user has to spend more time trying to reconstruct the structure again.

A stark contrast is shown in that the entire graph was known when created with Graphviz, and Graphviz consequently had full control over placement of the shapes. This is different to Visio where as the image was being drawn it was under the user's control. It was constructed iteratively, with nodes being moved around in the drawing, the properties of the nodes being edited, and nodes being added, and a few extra nodes not shown in the graph being added and subsequently deleted. The image shown in the right of Fig  is the result of the final layout of the final graph, but it clearly shows that the layout algorithm integrated into the tool did not handle well the incremental construction of the graph, and the control the user possessed in its creation and adjustment.

A problem that is encountered when using layout algorithms integrated into these tools is the tools' ability to allow the user to continue to modify the graph after the tool has applied a layout algorithm to the current graph. The graph drawn in Fig  shows a graph drawn in Omnigraffle that has been laid out by the tool using a layered style layout, after which a vertex in the graph has been moved. The resulting image shows that the tool hasn't responded very well to the user asserting control by continuing to modify the diagram. It has kept the presence of the dummy nodes added by the tool to the graph for use in the previously applied layout. In order to preserve the mental map of the user, after the user moved the vertex highlighted, the tool should have ideally relaid portions of the graph to try and avoid edge crossings and weird connector routing.

Neither of these tools applied good layouts to graphs drawn in them, and neither allowed the user to maintain the ultimate level of control. While these examples are extremely brief they start to show the current efforts in the interactive graph layout field, and why there is a need to try and develop something better.

Figure: A hierarchical layout in Omnigraffle, with a vertex manually moved