Since many aesthetic constraints are conflicting in nature, graph-drawing algorithms generally tend to optimize one or two constraints to the fullest. This paper introduces a new graph-drawing algorithm called BIGANGLE, which is built on the classical spring-embedder algorithm with two extra constraints for increasing the size of crossing angles and angular resolution of vertices. It shows empirically why this algorithm is better than the plain spring algorithm, based on a total of seven graph-drawing aesthetic criteria:
- Number of edge crossings;
- Average size of crossing angles;
- Standard deviation of crossing angles;
- Average of edge lengths;
- Standard deviation of edge lengths;
- Angular resolution; and
- Average of standard deviations of angular resolution.
The proposed algorithm makes compromises in aesthetic constraints rather than trying to satisfy them fully. The authors accomplish this by modifying the spring algorithm to include a cosine force to increase the size of the crossing angle and a sine force to increase the angular resolution of the vertices. This happens to improve the drawings on many other aesthetic criteria beyond the two intended ones. According to the authors, this result suggests that “aesthetics should not be considered separately.” Improving multiple aesthetics simultaneously, even to a small extent, will have a better chance of making the resulting drawings more effective in terms of cognitive load and visualization efficiency.
The authors then conduct a user study to compare their graph-drawing methodology to the original, recording users’ “task performance (measured as response time and accuracy) and the mental effort devoted [to] the task.” BIGANGLE outperforms the classical algorithm on all counts. This user study, used to measure the effectiveness of graph drawings, seems novel.
The results are especially interesting for people designing graph-drawing algorithms. However, I found it puzzling that the authors did not compare BIGANGLE with an algorithm that tries to fully satisfy only one of these criteria (say, maximizing the size of the crossing angle).
It also appears to me that the additional cosine and sine force calculations will add overhead during computation. This is supported by the average running time provided in Table 1. However, it is not clear whether the BIGANGLE algorithm will scale up to offset the increase.
