Lombardi Drawings

Lombardi drawings are drawings of graphs in the plane so that every edge is represented by a circular arc and every vertex has perfect angular resolution. The concept is inspired by artist Mark Lombardi, who used this iconic style to find patterns in complex networks of various kinds.

However, it is known that not every graph has a Lombardi drawing and not every planar graph has a planar Lombardi drawing. Thus, not every graph can be drawn in this style, unless we relax the strict requirements of the definition.

Lombardi Drawings from the competition held at the International Symposium on Graph Drawing (2011)

We introduce k-Lombardi drawings, in which each edge may be drawn with k circular arcs; we show that every graph has a smooth 2-Lombardi drawing and every planar graph has a smooth planar 3-Lombardi drawing.

For planar graphs, the big open question is whether every outerplanar Lombardi graph has a Lombardi drawing. We study planar Lombardi drawings for outerpaths, i.e., outerplanar graphs whose dual is a path. We show that every outerpath has an outerplanar Lombardi drawing and present a linear-time algorithm to construct it.