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.

Using a quadtree on top of a circle packing to draw planar graphs with few slopes

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.


None: 0xDE featured on my blog


I recently compiled a list of the 25 best Math blogs for college students, and I just wanted to let you know that you made the list! It is published online at http://www.onlinedegrees.org/25-best-math-blogs-for-college-students/

Thanks so much, and if you think your audience would find useful information in the list or on the site, please feel free to share the link. The blog is just starting up, so we always appreciate a link back as we're trying to increase readership.

Thanks again, and have a great day!