I was wondering whether the outerplanar strict confluent drawings I studied in a Graph Drawing paper last year had underlying diagrams whose treewidth is bounded, similarly to the treewidth bound for the usual outerplanar graphs. The confluent graphs themselves can't have low treewidth, because they include large complete bipartite graphs, but I was hoping that a treewidth bound for the diagram could be used to prove that the graphs themselves have low clique-width. Sadly, it turns out not to be true.

The drawing above, shown with two levels of cells surrounding the central pentagon, can be extended to any number of levels. Besides the three shapes of faces shown here (with three, four, and five sharp points) there's one more possible shape, with three sharp points that are not consecutive, that would take a couple more levels to complete — the five points on the boundary with three incoming edges would each form the base of one of these shapes — but that's the only other thing that can happen. The drawing is based on the order-5 pentagonal tiling of the hyperbolic plane, and consists of five-sided regions with five regions meeting at each confluent junction. By the theory from my GD paper, it's not possible to find a different drawing with the same vertices in the same order in which some junctions have been merged, reducing the treewidth of the drawing. And because it can be extended to arbitrarily large patches of the pentagonal tiling (analogous to arbitrarily large grids in the Euclidean plane) it has unbounded treewidth.

It doesn't seem to work to do this directly with the square grid because some confluent junctions will have three connections in one direction and one in the other, allowing them to be merged with a neighboring junction. Using a hyperbolic tiling pattern allows all junctions to have at least two connections in each direction.

(G+)