I have another new paper on the arXiv, "Treetopes and their graphs", arXiv:1510.03152. It's mostly about a class of 4-dimensional polytopes, and their connections to clustered planarity, but it's hard to visualize 4d, especially on a 2d screen. So to explain what's in the paper, let's start by analogy, several dimensions lower.

Suppose you have a cycle graph (you can think of this as being one-dimensional: just vertices connected to each other in a single loop). But you also have, separately from the graph itself, some sort of hierarchical clustering on the graph. Some paths within the cycle form clusters, and each pair of clusters of this clustering are either nested or disjoint. Then it will always be possible to represent both the graph and the clustering in a single drawing, something like this:

A clustered cycle graph

The clusters are drawn as curves (here, circles) surrounding subsets of vertices of the graph. Edges never cross each other, cluster boundaries never cross each other, and edges cross cluster boundaries only when they have to: when one endpoint of the edge is inside the cluster and one edge is outside. A drawing with these properties is called clustered planar. Clusters of paths in a cycle always have such a drawing, but more generally it's a big open problem in graph drawing to test whether a given planar graph and clustering can be drawn in this way. There are lots of special cases where we know how to find such a drawing, but we don't know of an algorithm that solves all the cases, and we don't know of any hardness result that would prevent such an algorithm from existing.

But back to the cycle. Choose a clustered drawing with no two curves that separate the points in the same way: if two clusters are complementary to each other, we only use a single curve for both of them. The cluster boundaries divide the plane (and the cycle vertices) into different regions; let's add a "cluster vertex" for each region, and connect it to the cluster vertices for neighboring regions and to the cycle graph vertices within its own region. The number of regions, and the number of cluster vertices, is one more than the number of curves you had; you can think of this as adding one more cluster to the clustering, containing all of the vertices in the graph. I call the resulting augmented graph a "cluster graph". Here's what we get for the same example:

Halin graph produced as the cluster graph of a clustered cycle graph

The result is a Halin graph! A Halin graph is usually described as being formed from a tree that has no degree-two vertices and is embedded in the plane, by adding a cycle of edges connecting the leaves of the tree in clockwise order with respect to the embedding. Instead, here, we started with the cycle and then added the tree later, but the result is the same. Any nested clustering of paths on a cycle graph will have a Halin graph as its cluster graph, and all Halin graphs can be formed in this way. Every Halin graph is itself planar. So we've taken a one-dimensional graph (a cycle graph), added a clustering, and shown how to form a special kind of two-dimensional graph (a planar graph) from it.

But Halin graphs are not just planar; they're a special case of the polyhedral graphs, the graphs of convex 3-polytopes, just as cycle graphs are the graphs of convex 2-polytopes (that is, convex polygons). A planar graph is the graph of a polyhedron exactly when it is 3-connected (it can't be broken into two pieces by removing only two vertices) and Halin graphs are always 3-connected; in fact, they were studied by Halin as examples of graphs that are minimally 3-connected (removing any edge from the graph breaks this property). The polyhedra that you get from Halin graphs go under several different names, but they can be defined very simply in terms of their face structure: the Halin graph polyhedron has one special two-dimensional "base" face such that every other two-dimensional face shares an edge with the base. When this is true, the edges that are not part of the base face form a tree, and the base face forms a cycle that passes through the leaves of this tree, just like for the standard graph-theoretical definition of a Halin graph.

So return once more to our cycle graph, its clustering, and the Halin graph that we get as its cluster graph. In graph-theoretic terms, we thought the cycle graph was one-dimensional and its planar cluster graph was two-dimensional. But when we look at them geometrically, really it seems that the cycle graph is two-dimensional (it's the graph of a convex polygon) and that its cluster graph is three-dimensional (it's the graph of a convex polyhedron). Can we bring this up another level, and turn three-dimensional graphs (the graphs of arbitrary convex polyhedra, not just Halin graphs) plus clusterings on those graphs (the still-mysterious clustered planar drawings) into four-dimensional objects?

Yes! (Otherwise, why would I have asked those questions.)

The same geometric definition of Halin graph polyhedra works equally well as the definition of a class of higher dimensional polytopes that I call treetopes. These are the polytopes where every 2-dimensional face meets a designated base face in an edge (equivalently where every face of dimension two or more has more than one vertex in common with the base case). These polytopes have many propertes in common with Halin graphs: for instance, the edges that are not part of the base face always form a tree. And in the four-dimensional case, these can be formed from the three-dimensional polyhedral graphs as the cluster graphs of a certain type of clustered planar drawing, and every such graph gives rise to a four-dimensional treetope in this way. Here's an example, of a clustered planar drawing of a polyhedral graph and of the cluster graph (the graph of a 4-polytope) that you get in this way:

The graph of a treetope as the cluster graph of a clustered polyhedral graph

You can see the three-dimensional faces that turn this into a four-dimensional polytope, if you squint: there's a Halin graph growing above each face of the planar part, rising to a peak at the common ancestor of the vertices in the face, and each of these forms a three-dimensional polyhedron, one of the 3-faces of a 4-treetope. This is true for the external face of the planar part as well as for each of its internal faces. Finally, the base face of the 4-treetope is given by the planar graph itself.

The proof that these clustered planar graphs are always the same thing as the corresponding 4-treetopes (and vice versa) uses an inductive construction in which one repeatedly collapses clusters down to single vertices or, in the other direction, blows up single vertices into their own little clusters with their own little polyhedral graphs inside the cluster. The same construction also leads to a polynomial time algorithm that can tell whether a given graph comes from a 4-treetope in this way, without having to be told which vertices are the ones on the base face and which of them represent clusters. We don't know of such an algorithm for the graphs of arbitrary 4-polytopes, and it seems that the problem should be hard for the existential theory of the reals, although we also don't know of a proof of such a hardness result.

There's also a bit at the end of the new paper about the sparsity properties of these graphs. In particular, by working with the clustered planar view of these graphs instead of the 4-dimensional polytope view, it's possible to show that they have small separators and bounded expansion, so many sparse graph algorithms work on these graphs. In contrast, 4-polytopes in general can be very far from sparse (they can be complete graphs).

But my proof that 4-treetopes have bounded expansion uses some of the special properties that their corresponding clustered planar drawings have. So this raises another question, that I don't know the answer to: suppose you're given a clustered planar drawing that does not meet the special conditions required for it to correspond to a 4-treetope. Just any clustered planar drawing. And then you construct the cluster graph of this drawing in the same way I described above. These graphs have constant edge/vertex ratio, because they are the union of a planar graph and a tree. But are they sparse in any stronger sense? Do they also have bounded expansion? I don't know.

(G+)