An ongoing concern in graph drawing research has been curve complexity. If you draw a graph using a certain style, how complicated are you going to have to make the edges? More complicated curves are harder for readers to follow, and therefore they make the graph less readable. But simpler curves (such as line segments) may have their own problems: not fitting the style (which may constrain the edges to certain directions), running through vertices, forming sharp angles with each other, etc. To balance these concerns, a lot of work in graph drawing has allowed edges to be polygonal paths but has tried to prove hard upper bounds on how many bends you need to use. I'm not fond of polylines and bends myself — I prefer smooth curves such as circular arcs meeting at inflection points — but in this case one can measure the curve complexity in terms of the number of arcs you need per edge, and the theory ends up being much the same.

A couple of examples: in the right angle crossing drawing style (RAC drawing), crossings are allowed, but the crossings have to be at right angles.

RAC drawings of K_5 and K_{3,4}

The examples above have no bends, but bendless RAC graphs are quite restrictive. In particular they can only have most 4n − 10 edges (as Didimo et al proved in their paper introducing RAC drawing). On the other hand, if you allow bends, it's easy to turn any drawing into a RAC drawing: insert new bends near each crossing to allow the edges that cross to form the correct angles with respect to each other. How many bends per edge do you need? Exactly three. The graphs with two-bend-per-edge RAC drawings are still limited to a linear number of edges, but three bends let you draw anything, with a layout like the one below for \( K_8. \)

K_8 drawn with right-angle crossings and three bends per edge

In another drawing style, three-page topological book embeddings, we wish to draw graphs on three half-planes in space, meeting at a 120 degree angle along a line. The vertices must be on this line, and the edges must be formed from semicircles within the half-planes.

Three-page book embedding of K_5

The graphs that can be drawn with only a single semicircle per edge form a restricted subclass of all graphs (again, with only a linear number of edges). However, all graphs can be drawn in a three-page book if the edges can be drawn as multiple semicircles that connect to each other across the spine of the drawing. Can we bound the number of spine crossings per edge that we might need?

In general, given some graph drawing style, and an appropriate notion of curve complexity within that style, we can ask similar questions. Does the style allow drawings of all graphs with bounded curve complexity? Or, if you impose a bound on the curve complexity, are you necessarily limiting the graphs you can draw to a restricted subclass of all graphs?

It turns out that questions like this can be formalized and answered using the theory of shallow minors and sparse classes of graphs, ably described by Jaroslav Nešetřil and Patrice Ossona de Mendez in their book Sparsity: Graphs, Structures, and Algorithms.

A shallow minor of a given graph is a minor (a smaller graph formed by edge contractions, edge deletions, and vertex deletions) such that the subsets of the original graph that are contracted into a single vertex in the minor have small diameter. The vertices of the shallow minor can be represented by a collection of low-diameter vertex-disjoint subtrees of the starting graph, such that two vertices of the minor are adjacent if and only if the two corresponding subtrees are connected by an edge. A shallow topological minor is almost the same but the subtrees can have only one vertex of degree greater than two, so that a subdivision of the minor (with few subdivision points per edge) forms a subgraph of the starting graph.

A family \( \mathcal{F} \) of graphs is said to be somewhere dense if there exists a diameter bound such that the shallow minors of graphs in \( \mathcal{F} \), with that bound, include all graphs (or all complete graphs). Otherwise, it is nowhere dense. You can state the same definitions with shallow topological minors and it ends up being equivalent to the version with shallow minors.

But now, suppose we have a drawing style for graphs with the following properties. First, removing edges or vertices from a drawing should result in another valid drawing. And second, there is a notion of bend points for the drawing, such that the curve complexity of a drawing in this style is the maximum number of bends per edge, and such that replacing a bend point by a degree-two vertex or vice versa also results in a valid drawing. Let \( \mathcal{F} \) be the family of graphs that can be drawn in this style with no bends. Then if every graph \( G \) can be drawn with bounded curve complexity, we can replace the bends in a drawing of \( G \) by subdivision points and get a graph in \( \mathcal{F} \) that has \( G \) as a shallow minor, so \( \mathcal{F} \) is somewhere dense. On the other hand, if \( \mathcal{F} \) is somewhere dense, we can generate a drawing with bounded curve complexity for any graph \( G \) by finding a graph in \( \mathcal{F} \) that has \( G \) as a shallow topological minor, drawing this bigger graph, removing the parts of the drawing that don't correspond to features of \( G \), and turning the subdivision points back into bends. So: the drawing style can represent all graphs, with bounded curve complexity, if and only if its family of bendless graphs is somewhere dense.

Let's look again at the two drawing styles we used as examples. Are the bendless RAC graphs somewhere dense? Yes, because we can draw all graphs in RAC style with only three bends. It's been claimed that RAC graphs are closely related to 1-planar graphs, but this shows a big difference between the two classes of graphs. In particular, unlike 1-planar graphs, the bendless RAC graphs do not have separator theorems, because if they did they would have bounded expansion, something that can only be true of nowhere-dense graph families.

Does every graph have a three-page topological book embedding with a constant number of spine crossings per edge? No, because the graphs with three-page book embeddings (without spine crossings) have bounded expansion, and therefore cannot be somewhere dense. In fact in this case it's known that logarithmically many crossings per edge might sometimes be needed and that this bound can always be achieved.

There's an odd mental inversion related to this phenomenon. In graph theory, being nowhere dense is thought of as good (it tells you your family has some interesting properties) and somewhere dense is bad (your family contains too many graphs to have any nice structure). But in graph drawing, it's the somewhere dense classes that are better than the nowhere dense ones: they describe the drawing styles that are sufficiently general-purpose to be usable for all graphs, with bounded curve complexity. So maybe it's the somewhere dense drawings styles (like RAC drawing) rather than the nowhere dense ones (like 1-planar drawing) that we should be paying more attention to.

(G+)