The cops-and-robbers definition of Treewidth is quite intuitive.
You have an undirected graph with a robber moving infinitely fast along the edges of the graph.
You have k cops, each driving their own very slow helicopter that can land on any vertex you want (but it takes some time). The cops can communicate and they know at any time where the robber is.
Given a graph, how many cops do you need to catch the robber, i.e., trap the robber on an edge?
In a tree: 2
On a cycle: 3
In an n × m grid graph: you need min(n, m) + 1.
---
In the game where the cops don't know where the robber is, the "width measure" is called pathwidth.
From wikipedia https://en.wikipedia.org/wiki/Carving_width#Related_paramete...:
“[…], it can be shown that for any graph, the carving width is greater than or equal to half the branch width, and is less than or equal to the degree times the branchwidth. Because treewidth and branchwidth are always within constant factors of each other, similar bounds can be used to relate carving width to treewidth.”
You have an undirected graph with a robber moving infinitely fast along the edges of the graph.
You have k cops, each driving their own very slow helicopter that can land on any vertex you want (but it takes some time). The cops can communicate and they know at any time where the robber is.
Given a graph, how many cops do you need to catch the robber, i.e., trap the robber on an edge?
In a tree: 2
On a cycle: 3
In an n × m grid graph: you need min(n, m) + 1.
---
In the game where the cops don't know where the robber is, the "width measure" is called pathwidth.