Geometric thickness of bounded degree graphs
Just in time for Graph Drawing, I've updated my page on geometric thickness to reflect an exciting new result of Barát, Matoušek, and Wood: bounded degree graphs may have unbounded geometric thickness, even approaching the square root of the number of vertices. This is in strong contrast to my SoCG 2004 paper with Duncan and Kobourov, which showed that degree four graphs have bounded geometric thickness.
The basic idea seems very simple, but nonconstructive: use counting arguments to compare the numbers of bounded degree graphs and low thickness graphs. For low bounds on the geometric thickness, there are few enough order types of point sets, and few enough ways of connecting the points in an order type into a small number of planar-straight-line layers, that not all bounded degree graphs can have a low-thickness representation. The authors also apply the same basic idea to some related problems of drawing with few edge slopes.
The basic idea seems very simple, but nonconstructive: use counting arguments to compare the numbers of bounded degree graphs and low thickness graphs. For low bounds on the geometric thickness, there are few enough order types of point sets, and few enough ways of connecting the points in an order type into a small number of planar-straight-line layers, that not all bounded degree graphs can have a low-thickness representation. The authors also apply the same basic idea to some related problems of drawing with few edge slopes.