Investigating Crossing Perception in 3D Graph Visualisation

The investigation of impact factors for graph perception is important to evaluate and improve quality measures and drawing algorithms as well as to better understand human graph perception. The number of edge crossings in a 2D graph drawing has long been a main quality measure for drawing evaluation and is still regularly investigated and reported. Their impact is however dependent on further factors such as graph size or crossing angle [6, 3, 9]. The use of stereoscopic 3D graph visualisations has gained attraction over the last years, and results from several studies indicate that they can improve analysis efficiency for a range of analysis scenarios [4, 1, 2, 7, 10]. The importance and effect of impact factors for perception might differ from the classical 2D setting, e.g. due to the influence of depth cues and eye depth focus. While edge crossings can also occur in 3D, there are edge configurations in space that are not crossings but might be perceived as such from a specific viewpoint. Such configurations create crossings when projected on the corresponding 2D image plane and could impact readability similar to 2D crossings. To indicate that most of such edge configurations are not edge crossings in 3D per se, but could be perceived as such, we call them ‘projective edge crossing configurations’, or ‘PECC’ in short. The additional depth aspect and the subsequent impact factor of edge distance in space might further influence the importance of those configurations for readability, and also change the influence of aspects such as the perceived crossing angle. We investigate the impact of such factors in an empirical study and report on findings of difference between major factor categories.

As an initial step to investigate the effect of PECCs on graph perception in S3D, we investigate their influence on task performance. As controlled impact factors that serve as independent variables for our study, we add the depth distance of the edges in 3D space at the projected crossing points (IV3) to the established criteria of number of crossings (IV1) and crossing angle (IV2) (which we measure in the projection as an indicator of the perceived number and angles). The study participants were asked to perform three established tasks on 3D graph visualisations in VR: shortest path (SP), common neighbours (CN), and memorisation (ME). We recorded the completion time and accuracy, and the participants were told to perform tasks as accurately and as quickly as they could, while the pace was controlled by the participant. We chose a VR environment for the study, as we could fully control the appearance of the environment and graphs to minimise distraction. The participants remained seated during the study, wearing a head-movement tracking VR HMD (Meta Quest 2), with graph visualisations shown centred in front of their viewpoint, see Figure 1. Except for small head movements, there is no interaction that allows the viewer to change the visual representation of the graphs, in order to avoid changes in the impact factor values. We implemented a Unity application based on the VR graph analysis framework GAV-VR [5].

For the stimuli, we restricted our study to a single graph generator model, the Newman-Watts-Strogatz random graph model, which allows to create graphs with a good combination of local clustering and shortest path lengths as often found in practice [8]. For the layout we decided to use a standard spring-model layout, which provides a reasonable readability for the tasks, as tested by us before the study. In order to test clearly separable conditions for our independent variables, the stimuli were categorised into factor levels as having either low or high number of (projection) crossings - up to $2$ (level L) and at least one per task-related edge on average (level H), crossing angles - below ${30}^{\circ }$ (level L) and above ${60}^{\circ }$ (level H), and crossing point distances - as fraction of full graph representation depth (up to $0.1$ level L and above $0.3$ level H). We calculate these variables task-related: Instead of measuring them across the whole graph, we investigate PECCs that are involving task-relevant edges, i.e. (shortest) path edges for SP and ME and edges adjacent to the selected nodes for CN. This results in eight conditions, encoded as XYZ in the following, where X indicates the level for IV1 (H for high, L for low), Y the level of the average IV2, and Z the level of the average IV3. We recruited $28$ participants ($12$ male, $16$ female) at our university, aged 19-36 years (avg. 24.46). Thirteen of them reported prior VR experience, and seven reported previous graph analysis experience. All participants reported normal or corrected-to-normal vision. We performed a within-subjects experiment and counter-balanced task and condition order.

We assumed that, in line with previous studies in 2D setups, it will be easier to perform the tasks with less crossings and larger angles, and in addition that larger edge distance would be the easier factor level, too. In summary, we have for accuracy significant differences between high and low PECC numbers (all tasks), but only for task SP between high and low angles and between high and low distances. For completion time (see Table 1), we recorded significantly shorter times for low PECC number combinations (LXX) across all tasks, shorter times for low angle combinations (XLX) for tasks SP and CN, and no significant differences for distance levels. We could see significant impact on both accuracy and completion time based on differences between pairs of conditions, but also between low and high levels of the number of PECC. Compared to known 2D results, we could observe similar effects for the number, but in contrast to 2D results no similar result for angles, which we deem an important find to be further investigated in future research. For depth impact, we established significant differences between high and low levels of PECC distance. Thus, we think that a deeper investigation of PECC impact factors should be a topic of future research to improve layout quality measures and algorithms for S3D.