<p>For question <span class="math-container">$1$</span>: any <em>bidimensional</em> parameter has this property on general graphs. A parameter <span class="math-container">$s(G)$</span> is bidimensional if the value of <span class="math-container">$s(G) \geq s(H)$</span> for every minor <span class="math-container">$H$</span> of <span class="math-container">$G$</span>, and if <span class="math-container">$s$</span> is ``large'' on grids.</p>
<p>In applications to PTASes, sub exponential algorithms and kernels on minor-free classes of graphs, &quot;large&quot; means that there exists a constant <span class="math-container">$c$</span>, such that the value of <span class="math-container">$s$</span> on a <span class="math-container">$t$</span> times <span class="math-container">$t$</span> grid is at least <span class="math-container">$ct^2$</span>. This is what you most likely will find if you do a google search for ``bidimensionality''</p>
<p>However, for your question it is sufficient that <span class="math-container">$s$</span> grows to infinity on <span class="math-container">$t$</span> times <span class="math-container">$t$</span> grids as <span class="math-container">$t$</span> grows to infinity. This is because any graph with large enough treewidth will contain a large enough grid minor. So, to conclude, if <span class="math-container">$s$</span>:</p>
<ul>
<li>is closed under minors</li>
<li>is arbitrarily large on <span class="math-container">$t$</span> times <span class="math-container">$t$</span> grids for large enough <span class="math-container">$t$</span></li>
</ul>
<p>Then s has the s-treewidth property. See the recent parameterized complexity book ( <a href="http://parameterized-algorithms.mimuw.edu.pl" rel="nofollow noreferrer">http://parameterized-algorithms.mimuw.edu.pl</a> ) in the treewidth chapter for more info.</p>

CC BY-SA 4.0
2016-08-25T07:26:44.903Z
2021-01-01T15:46:08.617Z
2021-01-01T15:46:08.617Z
daniello
<p>Among your list, (at least) vertex cover number and feedback vertex set size, for graphs in general.</p>

<ol>
<li><p>If a graph has a vertex cover of size at most $s$, then it has treewidth at most $\dots$ ?</p></li>
<li><p>If a graph has a feedback vertex set of size at most $s$, then it has treewidth at most $\dots$ ?</p></li>
</ol>

CC BY-SA 3.0
2016-08-24T02:13:44.070Z
2016-08-24T02:13:44.070Z
G Philip
<p>Let $s$ be a graph parameter (ex. diameter, domination number, etc)</p>

<p>A family $\mathcal{F}$ of graphs has the $s$-treewidth property if there is a function $f$ such that for any graph 
$G\in \mathcal{F}$, the treewidth of $G$ is at most $f(s)$.</p>

<p>For instance, let $s = \mathit{diameter}$, and $\mathcal{F}$ be the family of planar graphs. Then it is known that any planar graph of diameter at most $s$ has treewidth at most $O(s)$.
More generally, <a href="http://link.springer.com/article/10.1007/s004530010020" rel="noreferrer">Eppstein</a> showed that a family of graphs has the diameter-treewidth property if and only if it excludes some apex graph as a minor.
Examples of such families are graphs of constant genus, etc.</p>

<p>As another example, let $s = \mathit{domination{-}number}$. <a href="http://link.springer.com/chapter/10.1007/978-3-540-39658-1_22" rel="noreferrer">Fomin and Thilikos</a> have proved an analog result to Eppstein's by showing that a family of graphs has the domination-number-treewidth property
if and only if $\mathcal{F}$ has local-treewidth. Note that this happens if and only if $\mathcal{F}$ has the diameter-treewidth property. </p>

<p><strong>Questions:</strong>  </p>

<ol>
<li>For which graph parameters $s$ is the $s$-treewidth property known to hold on planar graphs?</li>
<li>For which graph parameters $s$ is the $s$-treewidth property known to hold on graphs of bounded local-treewidth? </li>
<li>Are there any other families of graphs, not comparable to graphs of bounded local-treewidth for which the $s$-treewidth property holds for some suitable parameter $s$? </li>
</ol>

<p>I have a feeling that these questions have some relation with the theory of <a href="http://publications.csail.mit.edu/abstracts/abstracts07/demaine_bidim/demaine_bidim.html" rel="noreferrer">bidimensionality</a>. Within this theory,
there are several important parameters. For instance, the sizes of feedback vertex set, vertex cover,
minimum maximal matching, face cover, dominating set, edge dominating set,
R-dominating set, connected dominating set, connected edge dominating set,
connected R-dominating set, etc.</p>

<ol start="4">
<li>Does any parameter $s$ encountered in bidimensionality theory have the $s$-treewidth property for some suitable family of graphs?</li>
</ol>

<graph-theory><graph-algorithms><treewidth><graph-minor>
Something-Treewidth Property
Springberg
# Something-Treewidth Property

(Asked by: username_0 on 2016-08-23)

Let $s$ be a graph parameter (ex. diameter, domination number, etc)

A family $\mathcal{F}$ of graphs has the $s$-treewidth property if there is a function $f$ such that for any graph
$G\in \mathcal{F}$, the treewidth of $G$ is at most $f(s)$.

For instance, let $s = \mathit{diameter}$, and $\mathcal{F}$ be the family of planar graphs. Then it is known that any planar graph of diameter at most $s$ has treewidth at most $O(s)$.
More generally, [Eppstein](http://link.springer.com/article/10.1007/s004530010020) showed that a family of graphs has the diameter-treewidth property if and only if it excludes some apex graph as a minor.
Examples of such families are graphs of constant genus, etc.

As another example, let $s = \mathit{domination{-}number}$. [Fomin and Thilikos](http://link.springer.com/chapter/10.1007/978-3-540-39658-1_22) have proved an analog result to Eppstein's by showing that a family of graphs has the domination-number-treewidth property
if and only if $\mathcal{F}$ has local-treewidth. Note that this happens if and only if $\mathcal{F}$ has the diameter-treewidth property.

**Questions:**

1. For which graph parameters $s$ is the $s$-treewidth property known to hold on planar graphs?
2. For which graph parameters $s$ is the $s$-treewidth property known to hold on graphs of bounded local-treewidth?
3. Are there any other families of graphs, not comparable to graphs of bounded local-treewidth for which the $s$-treewidth property holds for some suitable parameter $s$?

I have a feeling that these questions have some relation with the theory of [bidimensionality](http://publications.csail.mit.edu/abstracts/abstracts07/demaine_bidim/demaine_bidim.html). Within this theory,
there are several important parameters. For instance, the sizes of feedback vertex set, vertex cover,
minimum maximal matching, face cover, dominating set, edge dominating set,
R-dominating set, connected dominating set, connected edge dominating set,
connected R-dominating set, etc.

4. Does any parameter $s$ encountered in bidimensionality theory have the $s$-treewidth property for some suitable family of graphs?

**Tags:** graph-theory, graph-algorithms, treewidth, graph-minor

---

## 2 answers

### Answer by username_1 on 2016-08-25. Score: 6 | Accepted answer

For question $1$: any *bidimensional* parameter has this property on general graphs. A parameter $s(G)$ is bidimensional if the value of $s(G) \geq s(H)$ for every minor $H$ of $G$, and if $s$ is ``large'' on grids.

In applications to PTASes, sub exponential algorithms and kernels on minor-free classes of graphs, "large" means that there exists a constant $c$, such that the value of $s$ on a $t$ times $t$ grid is at least $ct^2$. This is what you most likely will find if you do a google search for ``bidimensionality''

However, for your question it is sufficient that $s$ grows to infinity on $t$ times $t$ grids as $t$ grows to infinity. This is because any graph with large enough treewidth will contain a large enough grid minor. So, to conclude, if $s$:

* is closed under minors
* is arbitrarily large on $t$ times $t$ grids for large enough $t$

Then s has the s-treewidth property. See the recent parameterized complexity book ( <http://parameterized-algorithms.mimuw.edu.pl> ) in the treewidth chapter for more info.


---

### Answer by username_2 on 2016-08-24. Score: 0

Among your list, (at least) vertex cover number and feedback vertex set size, for graphs in general.

1. If a graph has a vertex cover of size at most $s$, then it has treewidth at most $\dots$ ?
2. If a graph has a feedback vertex set of size at most $s$, then it has treewidth at most $\dots$ ?


---

