Something-Treewidth Property

Question

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 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 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. 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?

Answer 1

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 2

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$ ?