The widths of strict outerconfluent graphs
My newest preprint, “The widths of strict outerconfluent graphs”, arXiv:2308.03967, is centered on the graph drawn below, in a confluent style (meaning that two vertices are adjacent when there exists a smooth path connecting them through the drawing).
In some sense, it’s a continuation of my 2014 post here, “big grids in outerplanar strict confluent graphs”, which included a similar drawing. In that post, I already made the connection between the treewidth of the networks of curves used in a special class of drawings (the “strict outerconfluent” drawings of the title) and the clique-width of the graphs they represent. I had hoped to prove that strict outerconfluent graphs have bounded clique-width by using the structure of their drawings, but as that post demonstrated, the structure I wanted to use didn’t always exist. At that time I still didn’t know whether these graphs really had bounded clique-width, provable some other way. Now I know: they do not. The paper analyzes drawings like the one shown above (parameterized by the number of levels of arches) to demonstrate that the clique-width of strict outerconfluent graphs can be arbitrarily large.
If these graphs don’t have bounded clique-width, then what structure do they have instead? The answer is hinted at in the plural “widths” of the preprint title. They have bounded twin-width, a more general notion of width involving repeatedly merging pairs of vertices and keeping track of the degree of a “conflict graph” resulting when two merged vertices do not agree on which other vertices are their neighbors. The proof involves a counting argument (the number of strict outerconfluent drawings on a given ordered set of vertices grows only singly-exponentially); a more direct construction of a merge sequence for these graphs would be preferable, but I haven’t found such a construction yet.
It may be of interest to understand what a direct merge sequence construction looks like, for a simpler class of graphs and their drawings, the outerplanar graphs, although these are a very special case of more general known constructions. In more detail, what we want to construct is a sequence of pairwise merges of clusters of vertices, starting from a trivial clustering with one cluster per vertex. At each step, we have a graph with edges of two colors, black and red. Black edges (shown as yellow in the figure below) connect pairs of clusters for which all cluster-to-cluster edges are present in the original graph. Red edges connect pairs of clusters that have inconsistent adjacencies: some but not all cluster-to-cluster edges are present. We want to make sure that, at all times, the red edges form a low-degree graph.
For outerplanar graphs, it’s convenient to add artificial “blue” edges to the input graph, to make it into a maximal outerplanar graph, one in which every internal face is a triangle. Then, as we merge pairs of clusters, the clusters will be connected by black edges (all cluster-to-cluster edges present and real), blue edges (all cluster-to-cluster edges present but artificial), and red edges (inconsistent adjacencies). We’ll maintain an invariant that, after each step in the merge sequence construction, the graph remains maximal outerplanar and that its red edges lie only on the outer face, like the illustration below. If we can do this, it might look like we get twin-width two but actually it will be three because some steps will consist of two merges with a degree-three cluster temporarily created and then fixed.
The adjacencies of the triangles in any maximal outerplanar graph form a binary tree, which we can root arbitrarily and then find the farthest leaf from the root. The parent of this leaf has either one or two leaf children. This child or these children are triangles in the outerplanar graph, formed by two consecutive edges of the outer face and a diagonal connecting their endpoints. We can remove them from the graph by merging their middle vertices into the middle vertex of their parent triangle. If there is one child, the parent’s middle vertex has three neighbors before the merge and two after (it becomes a leaf); its two adjacent edges may become red, but that’s ok, because they’ll be on the outer face. If there are two children, then merging one of them may cause the middle vertex of the parent to temporarily have three red edges, but the second merge reduces that to two again. So the twin-width of these graphs is at most three.