The arXiv versions of my papers to appear later this month at Graph Drawing are now all available, so it seems like a good time to describe them all briefly here.

Lombardi drawings of graphs (arXiv:1009.0579, with Duncan, Goodrich, Kobourov, and Nöllenburg) is about a style of drawing we named in honor of artist Mark Lombardi, in which edges are drawn as circular arcs that are evenly spaced around each vertex. Lombardi used curved edges to great effect in his drawings of social networks describing conspiracy theories, and although he did not always evenly space these edges around the vertices it's obvious that he put some effort into maintaining nice spacing of the edges and vertices in his drawings. I posted earlier a link to my Lombardi Spirograph program, which makes drawings of this type for graphs with some sort of rotational symmetry; we also describe algorithms for finding Lombardi drawings of regular graphs, graphs in which every subgraph has a degree-two vertex, and several types of planar graphs. We left many problems open: for instance, does every 3-regular planar graph, or every outerplanar graph, have a planar Lombardi drawing? And what is the computational complexity of determining the existence of a Lombardi drawing with all vertices on a single circle for a 6-regular graph (equivalently, what is the complexity of testing whether a 6-regular graph contains either a Hamiltonian cycle or a bipartite 2-factor)?

Drawing trees with perfect angular resolution and polynomial area (arXiv:1009.0581, with the same authors) is about balloon drawings of trees: drawings in which each subtree of the tree is confined to a circle, with the root of the subtree at the center of the circle. As in our Lombardi drawing paper, we want the edges around each vertex to be perfectly evenly spaced. If we're allowed to permute the children of each node, but the edges have to be straight line segments, then by using standard techniques such as heavy path decomposition we can find a drawing of this type with polynomial area. But, if the ordering of the children is fixed, some trees might require exponential area. We show that Lombardi drawings can resolve the problem: by allowing the edges to be circular arcs instead of straight line segments, we can achieve both polynomial area and a pre-specified ordering of the children around each node.

Optimal 3D angular resolution for low-degree graphs (arXiv:1009.0045, with Löffler, Mumford, and Nöllenburg) is again about drawings with good angular resolution, but this time with polyline edges (sequences of straight line segments connected at bends) and in three dimensions. The molecular structure of the diamond provides an interesting infinite four-regular graph with optimal angular resolution for its vertex degree; we show that any degree-four graph can be drawn so that its vertices and edges lie along vertices and edges of the diamond lattice (although some of the graph edges may be considerably longer than the edges in the diamond lattice itself), achieving the same optimal angular resolution, while using only three bends per edge. Similarly, as I posted about last February, there exist infinite three-dimensional 3-regular graphs that live on the vertices and face diagonals of the integer grid and have perfect 120-degree angular resolution at each vertex; by using similar ideas, we can draw any degree-three graph in 3d so that it has the same angular resolution and two bends per edge (or, with nice grid coordinates, three bends per edge). Our drawings use polynomial volume but the polynomial is unlikely to be optimal: it should be possible to fit these drawings into cubical grids of side length sqrt(n), possibly at the expense of increasing the constant number of bends per edge. (Why the square root and not the cube root? Because the drawing needs to have linear cross-sectional area to allow enough edges to cross from one half to the other, in case the graph to be drawn is an expander graph.)

Drawing graphs in the plane with a prescribed outer face and polynomial area (arXiv:1009.0088, with Chambers, Goodrich, and Löffler) is in some sense the odd one out, as it has nothing to do with angular resolution. There's a style of drawing graphs embedded on higher-genus surfaces such as a torus, that involves cutting the surface along some of the edges of the graph to form a polygon called a "polygonal schema", and drawing the graph planarly within this polygon, with repeated vertices along the boundary where it was cut. For instance, I used something like this style in a recent blog post to show a graph on a torus, although I cheated a little because the top and bottom sides of the rectangle I drew don't line up with each other. Duncan, Goodrich, and Kobourov had a paper in GD2009 on this kind of drawing; they showed how to find the cut edges so that, in the rest of the graph, no edge goes from one of the sides of the polygonal schema back to the same side; this allows the shape of the outer face of the drawing to be fixed to the desired shape of the polygonal schema (with some vertices as corners and others having 180 degree angles along the edges of the schema) while still drawing all edges as straight line segments. For torus schemata (rectangles) they were able to show that a drawing of this kind needed only polynomial area, but for higher genus surfaces they were forced to resort to a spring embedding method of Tutte that allows the outer face's shape to be fixed but takes exponential area. In this paper we show that, for arbitrary choices of the outer face shape, it's possible to find a drawing with polynomial area. The method involves a divide-and-conquer structure in which we find a "river" (a path in the dual graph) that bisects the drawing, draw the two banks of the river recursively, and then draw vertices and edges that lie within the river.