Locally chordal graphs
Published:
My paper on locally chordal graphs appeared on arXiv! (See also: a recent talk I gave about this topic.) I’m very happy about this paper! In this post, I try to explain why.
Motivation
My interest in locally chordal graphs was inspired by a new theory that aims to distinguish between local and global structure in graphs.
The overall goal of distinguishing local and global structure in a graph is to be able to view a graph with varying levels of “focus,” bringing certain details into or out of view depending on our preference. For example, in the image below, we see a road map of Hamburg, and overlaid in red, a public transport map.
The public transport map is a coarser representation of the structure of the city than the road map. If you want to know how to walk to the vegan cafe nearby, or understand how the streets around your flat intersect the canal path, the road map is the more precise reference. But if you just want to understand the overall structure of the city — where there are holes around natural features like the lake and the park, or where the city gets denser downtown — the public transport map displays this information effectively, without getting lost in the cobblestone neighborhood streets.
To push the metaphor further, even the public transport map of the city is too detailed if what we want to do is get from Hamburg to, say, Harburg. In this situation, we’d want to zoom out even further, where the city now appears only as a cycle, with paths extending out to the surrounding areas.
Both map images were taken from OpenStreetMap at openstreetmap.org. Road networks are also used as an example to study local-global structure in this paper of Carmesin and Frenkel.
Along these lines, if you take an appropriately “coarse” view of any graph, you would observe what we might call its “global” structure. How can we formalize this idea?
A local-global framework
In the paper of Diestel, Jacobs, Knappe, and Kurkofka, they suggest a simple idea for how to define “local structure” of a graph: short cycles are local, and so is everything in the graph that is “generated” by short cycles. (For example, a wheel, shown below, contains a long cycle, but it is “generated by” triangles, so it counts as “local.”) Everything else is global.
A very nice feature of this definition of local is that it turns out to be equivalent to another intuitive definition of local: everything that appears in a small ball around some vertex is local, and everything else is global.
Left: a wheel. Right: The blue cycle is “local,” since it is in the second neighborhood of the teal vertex. The pink cycle, though it is the same length as the blue cycle, is not contained in the second neighborhood of any vertex, so it is “global.”
Test-driving the local-global framework: locally chordal
The broad goal of this theory is to be able to analyze local-vs-global structure in graphs generally. To approach this goal, it would be nice to start by understanding graphs whose global structure is particularly intuitive or visual. Graphs whose local structure is simple seem like good candidates for graphs whose global structure emerges in a natural way. See, for example, this $\infty$-shaped graph:
Just by looking, we can clearly see its global structure; namely, the $\infty$-shape. And, as we guessed, the intuitively clear global structure is complemented by simple local structure: in every small, “local” ball, the $\infty$-graph looks like cliques glued together in the shape of a tree. Graphs which look like trees glued together in the shape of a tree are the chordal graphs, which are very well-understood.
The main goal of our paper is to start with the assumption that local structure is simple, and derive results on global structure. Specifically, we tackle the following question:
What can we say about graphs whose local structure is chordal?
Locally chordal graphs
The answer is: a lot, it turns out.
Given a graph which is chordal, we can always find a tree-decomposition into cliques:
Left: A chordal graph. Middle: a tree-decomposition of the chordal graph. Right: The tree on which the tree-decomposition in the middle is modeled. This tree represents, roughly, the “global structure” of the chordal graph.
When we instead start with a graph that is locally chordal, instead of one big tree-decomposition into cliques, we get a collection of little tree-decompositions into cliques, one for every local part, i.e. ball of small radius, of the graph.
Our major result is that we can actually find a single global decomposition into cliques which “weaves together,” like solving a jigsaw puzzle, the collection of local tree-decompositions into cliques. There is no obvious reason why the local tree-decompositions should fit together nicely like puzzle pieces, so this is a surprising and pleasing result.
These decompositions witness that locally chordal graphs do, as we hoped, have a particularly intuitive and visual global structure: the global models are always of high girth. This is quite a natural condition to emerge as the global structure for locally chordal graphs. Because local structure is chordal, all short cycles of the graph appear in local tree-decompositions into cliques. Therefore, short cycles should not appear in the global model, which leads to a global model of high girth.
All in all, we prove that locally chordal graphs are exactly the graphs that look like cliques glued together in the shape of high-girth graphs, as illustrated by the $\infty$-shaped graph above. We also show that there is a simple and efficient algorithm to compute these global decompositions of locally chordal graphs.
The Upshot
The paper itself is a fun mix of different topics, including the theory of local-global structure and generalizations of properties of chordal graphs. Although it’s long, every section is basically independent, and it doesn’t need too much background to understand. In addition to the main result stated above, we manage to generalize many different characterizations of chordal graphs to locally chordal graphs, which was great fun for someone who spent a lot of time with chordal graphs in the past. Check it out, and send me an email if you have thoughts or questions!
What’s Next
For locally chordal graphs, we found decompositions which perfectly reflect the local-global dichotomy: local structure is represented by tree-decompositions into cliques, and global structure is represented by a high-girth global model. We have hope that this perspective on the local-global dichotomy has other intriguing applications; stay tuned!