Mental Models

When a reader views an image, they build in their mind a mental map of the structure of the graph. This is the reader's mind attempting to navigate and understand the information being presented. In a constantly changing graph, it is advantageous to help the drawer preserve their mental model, when graph layout occurs. This is to try reduce the effort taken by the user to rebuild their mental map in order to understand the new graph being viewed after a layout algorithm is applied.

Figure: () Current layout, () A new layout after inserting a new edge and rerunning layout algorithm, () A better layout, preserving the mental map. Reproduced from [6]

[] [] []

An example shown in Fig , shows that the graph depicted in Fig.  is a graph after an initial layout algorithm has been applied. If the user adds an edge from vertex 28 to 22, a layout that tries to preserve the mental map of the reader is shown in Fig. . By comparison the layout shown in Fig.  is at first glance different from Fig.  meaning the user has to spend more effort rebuilding their mental map, than with the graph in Fig. .

To attempt to obtain the goal of preserving a user's mental map as much as possible, Branke in [6] outlines two possible courses of action:

• Animate the changes to the graph as the layout algorithm is being applied, so that the transition is as smooth as possible in the users mind.
• Minimise the changes to the graph such that the effort to regain familiarity is minimal.

The second point is considered the hardest condition to meet. The reason stated by Misue et al. in [7], is that the majority of layout algorithms were designed around what they call layout creation, where in an interactive sense we want to preserve the mental map of the user through layout adjustment. Layout creation can be defined as taking a set of vertices and edges and creating a completely new layout for that set without taking into consideration any information about the positioning of the graph elements from a previous layout. This is how static graph layout tools operate. Layout adjustment is the layout algorithm taking into consideration the current state of the graph system, and any actions by the user, when the graph is relaid out. To further the goal of maintaining a user's mental map the underlying algorithm needs to be able to handle user interaction and adjust itself accordingly, something that IPSep-CoLa addresses in [24].

Part of constructing a good user interface is not only creating the ability to enter input efficiently, but to display output in a meaningful way. The current layout efforts of some current interactive editors will be discussed next, especially in relation to their output and its affect on the user's mental map.