# Natural (well studied) classes of graphs with treewidth $\Theta(n^\alpha)$ with $1/2 < \alpha < 1$

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

• FYI: There is another question for graphs with treewidth $o(n^{1/2})$: cstheory.stackexchange.com/questions/33753/… – delete000 Feb 6 '18 at 19:41
• 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 Feb 6 '18 at 21:33
• @MateusdeOliveiraOliveira Done. – delete000 Feb 7 '18 at 3:40

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.
• 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 Feb 8 '18 at 13:06