Splines for graph drawing theory
For a long time there has been a tension in graph drawing between theoretical and practical methods. Typical theoretical results show that graphs in certain special classes can be drawn with guaranteed bounds on certain measures of the drawing quality: for instance, the edges may be shaped as polylines with a hard limit on the number of bends per polyline, on the number of crossings per edge, and on the angle of each crossing. In practice we just want to draw arbitrary graphs and produce something legible. Few crossings and avoiding sharp angles are still good, but polylines are not: it can be difficult to distinguish bends from vertices or follow edges that repeatedly bend. For this reason, when straight line segments are inadequate, practical heuristics often use smooth curves rather than polylines, and especially spline curves.
Even when drawing graphs manually rather than in an automated way, splines can be very powerful at making a drawing more legible. Here’s an example I drew manually in 2010 for Wikipedia, a drawing of the Heawood graph demonstrating that it has crossing number \(\le 3\) despite the much higher number of crossings (14) of the more-symmetrical lead image of the linked Wikipedia article. For this example, replacing each spline with a line segment would preserve the low crossing number, but produce an uglier drawing with many sharp angles and nearby crossings. Instead, splines can be guided farther away from the other features of the drawing, producing a drawing with near-symmetry (only the bottom vertex is asymmetrically placed), near-right angle crossings, and all features well separated from each other.
My own research in this area has been very much on the theoretical side of things, but for a long time I’ve been exploring different ways of doing theory on graph drawings with curves instead of bends. This has included both confluent drawing, in which adjacencies follow curved paths through a drawing that resembles railroad tracks, and Lombardi drawing, in which edges are drawn conventionally as curves, but these curves are restricted to be circular arcs meeting at equal angles at each vertex. This works well for certain low-degree or symmetric graphs, knot diagrams, or even symmetric knot diagrams of torus knots. But graph drawing guru Peter Eades has argued (I think correctly) that for general-purpose graph drawing implementations, circular arcs are too rigid: instead, cubic Bezier splines are much more popular, and for good reason. It’s much easier to set up a spline between two vertices than a circular arc, you have greater and easier control of how the spline approaches its endpoints and how it gets between them, and yet spines are not so wiggly as to be difficult to follow by eye.
So what is my response to Eades’ critique? It is to continue doing theory, providing guarantees on measures of quality for drawings of special graphs, but now with splines instead of circular arcs. It’s still a different thing from implementing and testing practical but unguaranteeable heuristics, but with a course correction that I hope keeps the theory more closely in touch with practice.
Specifically, in the recent Symposium on Graph Drawing, I published a paper now also available on the arXiv: “Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature” (arXiv:2410.12083), with Michael Goodrich and Abraham Illickan, a new student of Mike. Here, a 1-planar graph is a graph that can be drawn in the plane with at most one crossing per edge; these graphs have been heavily studied since Ringel first defined them in 1965. Planar graphs can always be drawn with straight edges (Fáry’s theorem), but some 1-planar graphs such as the one below require curves or bends.
However, these curves do not need to be complicated: as our paper shows, cubic splines are enough. More, the splines can be chosen to ensure that all crossings are at right angles. An additional result of the paper is a drawing method for planar graphs with splines that meet at not-too-sharp angles, in a grid of polynomial area. However you draw a planar graph, the angles at its vertices are at least going to be inversely proportional to the degree, and our method achieves that. In contrast, for straight-line planar drawings, the angles may be much sharper: known methods produce angles that are exponentially sharp as a function of the degree, and inverse-cubic in the degree is necessary. Achieving angles that are bounded by any function of the degree, with straight edges, may require some edges to be exponentially longer than others. So, at least for these problems, splines are much more powerful than straight edges.