<p>This is not exactly what you are asking for, but it is very closely related and thus might be nevertheless interesting to you:</p>

<p>The concept of <em>local treewidth</em> introduced in <a href="http://dl.acm.org/citation.cfm?doid=504794.504798">M. Frick, M.Grohe, Deciding first-order properties of locally tree-decomposable structures</a> 
is more general than the definition of locally bounded treewidth
in the wikipedia article to which you refer.
For each graph $G$, the <em>local treewidth</em> of $G$ is the 
function $ltw^G$ which maps a radius $r$ to the maximum treewidth 
of $N^G_r(v)$ among all vertices $v$ of $G$, 
where $N^G_r(v)$ is the subgraph of $G$ induced by vertices at 
distance at most $r$ to $v$.
A class has <em>bounded local treewidth</em>, if there exists 
a function $f$ such that $ltw^G(r) \leq f(r)$ for each $r$ and each graph $G$ belonging to the class.</p>

CC BY-SA 3.0
2013-07-23T11:07:58.947Z
Indeed, this seems more general than the definition on Wikipedia. However, if one requires the class of graphs to be closed under induced subgraphs, the two definitions are equivalent. Note that the Frick-Grohe paper is also cited in the Wikipedia article.
Serge Gaspers
CC BY-SA 3.0
2013-07-23T08:45:54.957Z
2013-07-23T08:45:54.957Z
f-h
<p>The concept of exploiting properties that a graph possesses locally can be taken even further. Dawar, Grohe and Kreutzer in <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4276571&amp;tag=1" rel="noreferrer">Locally Excluding a Minor</a> considered classes of graphs that locally exclude a minor and Dvorak, Kral and Thomas in <a href="http://www.google.de/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;cad=rja&amp;ved=0CDgQFjAA&amp;url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.170.9781%26rep%3Drep1%26type%3Dpdf&amp;ei=NGNAUufoHcjbtAaJiICgAQ&amp;usg=AFQjCNFxR9H8EPgGXVd1J0sZOEsIESluvw&amp;sig2=kavqOZtvQqXu3hCpAgmZ8Q&amp;bvm=bv.52434380,d.Yms" rel="noreferrer">Deciding first-order properties for sparse graphs</a> considered classes of graphs that have (locally) bounded expansion. </p>

<p>Both of those classes are subsumed by classes of nowhere dense graphs, introduced by Nesetril and Ossona de Mendez.</p>

<p>Grohe announced this week at the <a href="http://highlights-conference.org" rel="noreferrer">Highlights conference</a> that Grohe, Kreutzer and Siebertz. have proved that every property of graphs definable in first-order logic can be solved in almost linear time on nowhere dense classes of graphs. This implies many fixed-parameter tractability results on nowhere dense graphs, e.g. for the (connected) dominating set and digraph kernel (both parameterized by the size of the solution), Steiner tree (parameterized by the size of the tree) and circuit satisfiability (parameterized by the depth of the circuit and the Hamming weight of the solution).  </p>

CC BY-SA 3.0
2013-09-23T16:00:15.373Z
2013-09-24T05:20:11.820Z
2013-09-24T05:20:11.820Z
Sebastian Siebertz
<p>Is the following graph class known in the literature?</p>

<p>The class of graphs is parameterized by positive integers $d$ and $t$ and contains each graph $G=(V,E)$ such that for each vertex $v\in V$, the subgraph of $G$ induced on all vertices at distance at most $d$ from $v$ in $G$ has treewidth at most $t$.</p>

<p>It generalizes the concept of <a href="http://en.wikipedia.org/wiki/Treewidth#Diameter_and_local_treewidth">locally bounded treewidth</a>, and it seems useful when searching for local structures in graphs.</p>

<reference-request><graph-theory><treewidth>
Generalization of locally bounded treewidth graphs
Serge Gaspers
# Generalization of locally bounded treewidth graphs

(Asked by: username_0 on 2013-07-22)

Is the following graph class known in the literature?

The class of graphs is parameterized by positive integers $d$ and $t$ and contains each graph $G=(V,E)$ such that for each vertex $v\in V$, the subgraph of $G$ induced on all vertices at distance at most $d$ from $v$ in $G$ has treewidth at most $t$.

It generalizes the concept of [locally bounded treewidth](http://en.wikipedia.org/wiki/Treewidth#Diameter_and_local_treewidth), and it seems useful when searching for local structures in graphs.

**Tags:** reference-request, graph-theory, treewidth

---

## 2 answers

### Answer by username_2 on 2013-09-23. Score: 11 | Accepted answer

The concept of exploiting properties that a graph possesses locally can be taken even further. Dawar, Grohe and Kreutzer in [Locally Excluding a Minor](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4276571&tag=1) considered classes of graphs that locally exclude a minor and Dvorak, Kral and Thomas in [Deciding first-order properties for sparse graphs](http://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CDgQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.170.9781%26rep%3Drep1%26type%3Dpdf&ei=NGNAUufoHcjbtAaJiICgAQ&usg=AFQjCNFxR9H8EPgGXVd1J0sZOEsIESluvw&sig2=kavqOZtvQqXu3hCpAgmZ8Q&bvm=bv.52434380,d.Yms) considered classes of graphs that have (locally) bounded expansion.

Both of those classes are subsumed by classes of nowhere dense graphs, introduced by Nesetril and Ossona de Mendez.

Grohe announced this week at the [Highlights conference](http://highlights-conference.org) that Grohe, Kreutzer and Siebertz. have proved that every property of graphs definable in first-order logic can be solved in almost linear time on nowhere dense classes of graphs. This implies many fixed-parameter tractability results on nowhere dense graphs, e.g. for the (connected) dominating set and digraph kernel (both parameterized by the size of the solution), Steiner tree (parameterized by the size of the tree) and circuit satisfiability (parameterized by the depth of the circuit and the Hamming weight of the solution).


---

### Answer by username_1 on 2013-07-23. Score: 9

This is not exactly what you are asking for, but it is very closely related and thus might be nevertheless interesting to you:

The concept of *local treewidth* introduced in [M. Frick, M.Grohe, Deciding first-order properties of locally tree-decomposable structures](http://dl.acm.org/citation.cfm?doid=504794.504798)
is more general than the definition of locally bounded treewidth
in the wikipedia article to which you refer.
For each graph $G$, the *local treewidth* of $G$ is the
function $ltw^G$ which maps a radius $r$ to the maximum treewidth
of $N^G\_r(v)$ among all vertices $v$ of $G$,
where $N^G\_r(v)$ is the subgraph of $G$ induced by vertices at
distance at most $r$ to $v$.
A class has *bounded local treewidth*, if there exists
a function $f$ such that $ltw^G(r) \leq f(r)$ for each $r$ and each graph $G$ belonging to the class.

> **Comments:**
> **username_0**: Indeed, this seems more general than the definition on Wikipedia. However, if one requires the class of graphs to be closed under induced subgraphs, the two definitions are equivalent. Note that the Frick-Grohe paper is also cited in the Wikipedia article.  

---

