Planar split thickness

I have a few new additions to my unmet-coauthor list in my latest arXiv preprint, "On the Planar Split Thickness of Graphs", arXiv:1512.04839, to appear at LATIN 2016.

The paper is on the following kind of graph drawing, where we draw each vertex multiple times (with labels so you can see which vertices are repeated where). To interpret the drawing, take the union of the adjacencies of the copies. For instance, the vertex d, repeated at the top of the drawing and the lower center, is adjacent to 6, 7, 2, 3, 0 (from the top), and also to 1, 4, 5, 8, 9 (from the bottom). If you check more carefully you'll see that each letter-digit pair is adjacent, so this is a complete bipartite graph.

This drawing style is related to graph minors (where the repeated copies of each vertex need to form a connected subgraph) and graph thickness (where only one copy of each vertex is allowed per connected component of the drawing) but without the constraints of either, allowing a little more flexibility in what can be drawn with a given amount of repetition. For instance, the complete bipartite graphs \( K_{6,10} \) (shown above), \( K_{5,16}, \) and \( K_{7,8} \) can all be drawn this way with only two repetitions per vertex, but cannot be drawn with thickness two.

Unfortunately, it's \( \mathsf{NP} \)-hard to find a drawing of this type with as few repetitions per vertex as possible. But fortunately, there are some important special cases where it's not so hard. In particular, one of our results is to solve the problem on graphs of bounded treewidth. The algorithm uses Courcelle's theorem, so there's probably a lot of room to make it more practical...