The origin of the notion of treewidth My question today is (as usual) a bit silly; but I would request you to kindly consider it.

I wanted to know about the genesis and/or motivation behind the treewidth concept. I sure understand that it is used in FPT algorithms, but I do not think that that was the reason why this notion was defined.

I have written up the scribe notes on this topic in the class of Prof Robin Thomas. I think I understand some of the applications of this concept (as in it transfers separation properties of the tree to the graph decomposed), but for some reason I am not really convinced that the reason this concept was developed was to measure closeness of a graph to a tree.

I will try to make myself more clear (I am not sure if I can, please let me know if the question is not clear). I would like to know if similar notions existed elsewhere in some other branch of mathematics from where this notion was supposedly "borrowed". My guess will be topology -- but owing to my lack of background, I cannot say anything.

The primary reason as to why I am curious about this would be -- the first time I read its definition, I was not sure why and how would anyone conceive of it and to what end. If the question is not still clear I would finally try stating it this way - Let us pretend the notion of treewidth did not exist. What natural questions (or extensions of some mathematical theorems/concepts) to discrete settings will lead one to conceive of a definition (let me use the word involved) as treewidth's.
Here's how you could come up with tree-width concept yourself.

Suppose you want to count the number of independent sets in the following graph.



Independent sets can be partitioned into ones where top node is occupied, and ones where it is unoccupied



Now, notice that knowing whether top node is occupied, you can count number of independent sets in each subproblem separately, and multiply them. Repeating this process recursively gives you an algorithm to count independent sets based on graph separators.



Now, suppose you no longer have a tree. This means separators are bigger, but you can use the same idea. Consider counting independent sets in the following graph.



Use the same idea of breaking the problem into subproblems on the separator you get the following



Like in the previous example, each term in the sum decomposes into two smaller counting tasks across the separator.





Note that we have more terms in the sum than in the previous example because we have to enumerate over all configurations on our separator, which can potentially grow exponentially with size of the separator (size 2 in this case).

Tree decomposition is a data-structure to compactly store these recursive partitioning steps. Consider the following graph and its tree decomposition





To count using this decomposition you'd first fix values in nodes 3,6 which breaks it into 2 subproblems. In the first subproblem you'd additionally fix node 5, which breaks its part into two smaller subparts.

Size of the largest separator in an optimal recursive decomposition is precisely the tree width. For larger counting problems, size of the largest separator dominates the runtime, which is why this quantity is so important.

As to the notion of tree-width measuring how close graph is to a tree, one way to make it intuitive is to look at the alternative derivation of tree decomposition -- from correspondence with chordal graphs. First triangulate the graph by traversing vertices in order and interconnecting all "higher ordered" neighbors of each vertex.



Then construct tree decomposition by taking maximal cliques and connecting them iff their intersection is a maximal separator.



Recursive separator and triangulation based approaches of constructing tree decomposition are equivalent. Tree width+1 is the size of the largest clique in optimal triangulation of the graph, or if the graph is already triangulated, just size of the largest clique.

So in a sense, chordal graphs of treewidth tw can be thought of as trees where instead of single nodes we have overlapping cliques of size at most tw+1. Non-chordal graphs are such "clique trees" with some clique edges missing

Here are some chordal graphs and their tree-width.