Basser Seminar Series

Larger Crossing Angles Make Graph Visualizations Easier To Understand

Speaker: Dr Tony Huang
CSIRO Computational Informatics, Australia

Time: Wednesday 11 September, 4:00-5:00pm
Refreshments will be available from 3:30pm

Location: The University of Sydney, School of IT Building, Lecture Theatre (Room 123), Level 1

Add seminar to my diary

Abstract

A great deal of real world data has a relational or graph structure. Data sets of such a structure are often visualized into node-link diagrams for a better understanding of them. However, the same graph can be drawn in indefinitely ways by simply changing the layout and different layouts affect human graph comprehension differently. In graph drawing, drawing principles, or aesthetics, have been proposed to produce quality layout. Among those aesthetics, edge crossings have been identified as the most important, having the greatest negative impact on humans. Subsequently, much effort has been devoted to crossing minimization in the design of graph drawing algorithms. However, crossing minimization is NP-hard. Further, algorithms that are designed for crossing minimization are often difficult to understand and implement, limiting practical use. A question that has long been asked is: is it possible to achieve a better or the same level of layout quality if we do not minimize the number of crossings?

In this talk, Dr Huang will introduce his research that led to a positive answer to this question and a finding of a new aesthetic: crossing angles. This talk will start with an exploratory eye tracking study of how people read graphs. This study revealed a surprising finding that crossings may not as bad as we normally think. He will demonstrate that a drawing with large-angle crossings can be as good as a drawing with no crossings and that the negative impact of crossings can be minimized or eliminated by maximizing crossing angles.

As an addition note, the finding of this new aesthetic shows that the classical criteria that were used for the previous 25 years to judge the quality of graph visualization were inadequate and has sparked a new research direction in the field, which is to represent graphs with large crossing angles called RAC (Right Angle Crossing) and LAC (Large Angle Crossing) drawings.

Speaker's biography

Dr Huang is a researcher from CSIRO, Australia. He is also affiliated with the University of Sydney, from which he received his PhD in Computer science in 2007. He has been active in visualization and HCI research and has over 60 publications. For more information,
Dr Tony Huang, CSIRO Computational Informatics, Australia.