Crossings vs crossing angle in graph drawing

It seems to be the standard position in graph drawing research that edge crossings are bad, and that minimizing crossings is a good way to make a drawing better. So I was interested to see a new preprint, “An Eye Tracking Study into the Effects of Graph Layout,” by Weidong Huang, which argues that crossings themselves are not so harmful, but rather that it is the crossings with sharp crossing angle that most confuse readers of the drawings. Huang bases these conclusions on actual experiments with actual humans, something I think there hasn't been enough of in the graph drawing community.

This should mean, for instance, that the two-layer drawings produced by my paper with Duncan and Kobourov on geometric thickness of low degree graphs should generally be quite legible, as the edges in one layer are generally horizontal while the edges in the other layer are generally vertical, producing nearly right angled crossings. For instance, here's a drawing of this type of the Nauru graph; I've been using this drawing as a bad example in some of my talks (because it doesn't indicate the graph's high degree of symmetry) but in terms of legibility of individual vertices and edges I think it's pretty good, even at this small size.

In this drawing the angular resolution at the vertices is much worse than at the crossings, so maybe that's a tradeoff to be explored. Probably there are some interesting additional algorithmic problems to be solved involving finding drawings with good angular resolution at the crossings.

Comments:

mcfnord:
2008-10-28T19:05:28Z

Like the art in this episode. Part prehistoric, part jazz, baby.