<p>The intersection graph of interior disjoint balls in $\mathbb{R}^d$, should have treewidth $O(n^{1-1/d})$, if there is justice in the universe (let me think about it - yep - there is). The treewidth should be $\Theta(n^{1-1/d})$. This family of graphs is contained in the family of graphs of low density graphs in $\mathbb{R}^d$. I have a paper (with Kent Quanrud) on low density graphs: <a href="http://sarielhp.org/p/14/low_density/low_density.pdf" rel="nofollow noreferrer">http://sarielhp.org/p/14/low_density/low_density.pdf</a>. Sorry for the shameless self promotion, etc.</p>

CC BY-SA 3.0
2018-02-07T19:16:56.033Z
You got that footnote into the published version! You, sir, have my eternal respect.
delete000
CC BY-SA 3.0
2018-02-08T05:18:52.993Z
Thank you. You are right! The footnote is in the official SICOMP version...
Sariel Har-Peled
CC BY-SA 3.0
2018-02-08T05:24:37.937Z
BTW, the bible on such things is the book Sparsity: http://www.springer.com/us/book/9783642278747
Sariel Har-Peled
CC BY-SA 3.0
2018-02-08T13:06:00.507Z
Thanks, digging into it now. Regarding your work: do sublinear separators in these classes of graphs imply subexponential _exact_ algorithms, in analogy to planar graphs with $O(\sqrt{n})$ separators, at least for some classes of problems?
delete000
CC BY-SA 3.0
2018-02-08T16:57:27.180Z
Yes. They should. We didn't look into that because (A) the paper is already long, (B) at this point, it seems like one should just state such algorithms for polynomial expansion graphs (i.e., graphs that have hereditary sublinear separators), and (C) we did not have any interesting example of such algorithms.
Sariel Har-Peled
CC BY-SA 3.0
2018-02-07T17:40:05.943Z
2018-02-08T05:20:59.560Z
2018-02-08T05:20:59.560Z
Sariel Har-Peled
<p>Which natural (well studied) classes of graphs have treewidth that scales as $\Theta(n^\alpha)$ in the number $n$ of vertices, with $1/2 &lt; \alpha &lt; 1$?</p>

CC BY-SA 3.0
2018-02-06T19:41:18.457Z
FYI: There is another question for graphs with treewidth $o(n^{1/2})$: https://cstheory.stackexchange.com/questions/33753/classes-of-graphs-with-superconstant-treewidth
delete000
CC BY-SA 3.0
2018-02-06T21:33:10.760Z
If you don't impose more restrictions then just take a clique with $n^{\alpha}$ vertices and connect it to a line with $n-n^{\alpha}$ vertices. Then the treewidth is $\Theta(n^{\alpha})$. To avoid such trivial answers, it would be good to reformulate the question to something like. "Which natural (well studied) classes of graphs have treewidth $n^{\alpha}$?" But even with such rephrasing it is very easy to come up with artificial examples.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2018-02-07T03:40:35.717Z
@MateusdeOliveiraOliveira Done.
delete000
<graph-theory><treewidth>
Natural (well studied) classes of graphs with treewidth $\Theta(n^\alpha)$ with $1/2 < \alpha < 1$
delete000
# Natural (well studied) classes of graphs with treewidth $\Theta(n^\alpha)$ with $1/2 < \alpha < 1$

(Asked by: username_0 on 2018-02-06)

Which natural (well studied) classes of graphs have treewidth that scales as $\Theta(n^\alpha)$ in the number $n$ of vertices, with $1/2 < \alpha < 1$?

**Tags:** graph-theory, treewidth

> **Comments:**
> **username_0**: FYI: There is another question for graphs with treewidth $o(n^{1/2})$: https://cstheory.stackexchange.com/questions/33753/classes-of-graphs-with-superconstant-treewidth  
> **username_1**: If you don't impose more restrictions then just take a clique with $n^{\alpha}$ vertices and connect it to a line with $n-n^{\alpha}$ vertices. Then the treewidth is $\Theta(n^{\alpha})$. To avoid such trivial answers, it would be good to reformulate the question to something like. "Which natural (well studied) classes of graphs have treewidth $n^{\alpha}$?" But even with such rephrasing it is very easy to come up with artificial examples.  
> **username_0**: @MateusdeOliveiraOliveira Done.  

---

## 1 answers

### Answer by username_2 on 2018-02-07. Score: 10 | Accepted answer

The intersection graph of interior disjoint balls in $\mathbb{R}^d$, should have treewidth $O(n^{1-1/d})$, if there is justice in the universe (let me think about it - yep - there is). The treewidth should be $\Theta(n^{1-1/d})$. This family of graphs is contained in the family of graphs of low density graphs in $\mathbb{R}^d$. I have a paper (with Kent Quanrud) on low density graphs: <http://sarielhp.org/p/14/low_density/low_density.pdf>. Sorry for the shameless self promotion, etc.

> **Comments:**
> **username_0**: You got that footnote into the published version! You, sir, have my eternal respect.  
> **username_2**: Thank you. You are right! The footnote is in the official SICOMP version...  
> **username_2**: BTW, the bible on such things is the book Sparsity: http://www.springer.com/us/book/9783642278747  
> **username_0**: Thanks, digging into it now. Regarding your work: do sublinear separators in these classes of graphs imply subexponential _exact_ algorithms, in analogy to planar graphs with $O(\sqrt{n})$ separators, at least for some classes of problems?  
> **username_2**: Yes. They should. We didn't look into that because (A) the paper is already long, (B) at this point, it seems like one should just state such algorithms for polynomial expansion graphs (i.e., graphs that have hereditary sublinear separators), and (C) we did not have any interesting example of such algorithms.  

---

