Crossing resolution of bounded-degree graphs

Two of the papers presented today at Graph Drawing (and one earlier at WADS) concerned drawings in which edges that cross are required to do so at a high angle. One of today's papers ("On the perspectives opened by right angle crossing drawings", by Angelini et al) included some results on bounded degree graphs, showing that graphs with sufficiently low degree bounds could be given drawings with right-angled crossings and few bends per edge. The other paper ("Area, curve complexity, and crossing resolution of non-planar graph drawings", by Di Giacomo et al) generalized the problem, looking not just at right angled drawings but at drawings in which all crossings have an angle bounded away from zero; the "crossing resolution" of the title is the minimum angle of any crossing. So what if we put both of these together and look at the crossing resolution of bounded-degree graphs?

As I already pointed out a year ago, an algorithm from a paper with Duncan and Kobourov in SoCG 2004 already achieves good crossing angles with no bends when the degree is very small (at most three). This algorithm draws the graph with its vertices on a grid and its edges in two planar layers such that one layer of the edges connects pairs of vertices on adjacent grid columns (causing them to be close to vertical) and the other layer connects pairs of vertices on adjacent grid rows (causing them to be close to horizontal). Two edges can cross only if all four of their endpoints lie on distinct rows and columns of the grid, ruling out what would otherwise be some bad cases. So the worst case appears to be one in which a slope-\( 3 \) and a slope-\( 1/3 \) edge cross each other, with angle \( \pi/2 - 2\tan^{-1}(1/3) \), approximately \( 53^\circ \).

A limit to the vertex degree bounds that force bendless drawings with high crossing resolution to exist is provided by a paper by Barát, Matoušek, and Wood that proves that graphs with degree nine may have unbounded geometric thickness. A drawing in which all crossings have angles bounded away from zero has bounded geometric thickness: if one partitions the edges of the graph into a constant number of subsets within which all slopes are close to each other, each subset must form a planar graph. So, since degree-9 graphs don't have bounded geometric thickness, they also don't have bounded crossing resolution.

For bendless drawings of graphs with degree from four to eight, it seems that it is still unknown how the crossing resolution may depend on the degree. And even for degree three, perhaps better crossing resolution may be achieved by some other algorithm.

ETA: János Pach points out that the same relation between geometric thickness and crossing resolution allows one to prove an \( O(1/n) \) bound on the crossing resolution of n-vertex complete graphs from known results on geometric thickness of complete graphs, improving a logarithmic bound from the Di Giacomo et al paper and an \( O(1/\sqrt{n}) \) bound obtained from a result of Aronov et al. that any \( n \) points in general position have \( \Omega(\sqrt{n}) \) pairwise crossing line segments.

Comments: