Planar drawings with few slopes

I should have waited a few more days to post about new graph drawing papers on the arXiv, because another nice one just showed up (presumably, for the same reason as my ones: the Graph Drawing 2010 proceedings versions are almost due).

It's called Drawing planar graphs of bounded degree with few slopes (arXiv:1009.1315), by Balázs Keszegh, János Pach, and Dömötör Pálvölgyi. There are several results in it, but the main one is that, for any constant d, there exists another constant s such that the planar graphs of degree at most d can be drawn planarly, with the edges as straight line-segments that have only s different slopes.

The proof is pretty, easy to explain, and uses some important and deep machinery about the geometric representation of graphs: the circle packing theorem of Koebe, Andreev, and Thurston. This theorem states that any planar graph can be represented by a system of circles with disjoint interiors, in such a way that the vertices of the graph correspond one-for-one with the circles, and with two vertices connected by an edge if and only if the corresponding circles are tangent. You can then get a planar straight line drawing by putting each vertex at the center of its circle, but that's not what Keszegh et al do.

Instead, they use a modified version of the circle packing theorem that works only on graphs of bounded degree, and imposes an additional constraint on the circles: any two adjacent circles have radii that are within a constant factor of each other. They then superimpose a quadtree on the circles, with the squares of the quadtree subdivided to a small enough size to ensure that there is a quadtree corner near each circle center, and they use these quadtree corners as the locations of the vertices of the drawing.

Because any two neighboring circles have similar sizes, the corresponding graph vertices will be rounded to quadtree corners at a similar grid resolution, and in the grid of that resolution the two neighboring vertices will be a constant number of grid cells apart from each other. Therefore, the slope is a rational number with small integer numerator and denominator, and there are only a bounded number of possible slopes; for instance in the drawing above the only slopes are –1, 3, 1/3, 5, 1/5, and -3/5. Although the authors don't emphasize this, their drawing also has bounded angular resolution.

Although pretty in theory, there are some practical issues with their method, partly because circle packings are difficult to calculate exactly and partly because the dependence of \( s \) on \( d \) is badly exponential. Possibly for this reason, the authors also describe alternative methods that allow a small number of bends in the edges but that greatly reduce the number of slopes needed in their drawings.

Comments: