Drawing graphs with large angle crossings: RAC and LAC drawing


It is well established that edge crossings inhibit human understanding; thus minimising the number of crossings became the most important criteria in graph drawing, and there has been a great deal of mathematical research on minimum crossing numbers by mathematicians. Recently, using human experiments, we showed that edge crossings do not inhibit human understanding if they cross with large angles.
This result spawned a new theory in graph drawing and combinatorial geometry on graph representations with large crossing angles, called RAC (Right Angle Crossing) and LAC (Large Angle Crossing) drawings. My initial papers on this have high citations. It is interesting that citations to this paper are evenly split between theoreticians (graph theorists, geometers) and applied researchers (information visualisation and in the application domains).


W. Huang, S. Hong and P. Eades, "Effects of Crossing Angles", Proceedings of IEEE Pacific Visualization Symposium (PacificVis 2008), IEEE, pp. 41-46, 2008.

In visualizing graphs as node-link diagrams, it is commonly accepted and employed as a general rule that the number of link crossings should be minimized whenever possible. However, little attention has been paid to how to handle the remaining crossings in the visualization. The study presented in this paper examines the effects of crossing angles on performance of path tracing tasks. It was found that the effect varied with the size of crossing angles. In particular, task response time decreased as the crossing angle increased. However, the rate of the decrease tended to level off when the angle was close to 90 degrees. One of the implications of this study in graph visualization is that just minimizing the crossing number is not sufficient to reduce the negative impact to the minimum. The angles of remaining crossings should be maximized as well.



Q. Nguyen, P. Eades, S. Hong and W. Huang, "Large Crossing Angles in Circular Layouts", Proceedings of Graph Drawing 2010, LNCS, pp. 397-399, 2011.

Recent empirical research has shown that increasing the angle of crossings reduces the effect of crossings and improves human readability. In this paper, we introduce a post-processing algorithm, namely MAXCIR, that aims to increase crossing angles of circular layouts by using Quadratic Programming. Experimental results indicate that our method significantly increases crossing angles compared to the traditional equal-spacing algorithm, and that the running time is fairly negligible.



Emilio Di Giacomo, Walter Didimo, Peter Eades, Seok-Hee Hong, Giuseppe Liotta: Bounds on the crossing resolution of complete geometric graphs. Discrete Applied Mathematics 160(1-2): 132-139 (2012)

The crossing resolution of a geometric graph is the minimum crossing angle at which any two edges cross each other. In this paper, we present upper and lower bounds to the crossing resolution of the complete geometric graphs.