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

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

  • 1
    $\begingroup$ You got that footnote into the published version! You, sir, have my eternal respect. $\endgroup$ – delete000 Feb 7 '18 at 19:16
  • $\begingroup$ Thank you. You are right! The footnote is in the official SICOMP version... $\endgroup$ – Sariel Har-Peled Feb 8 '18 at 5:18
  • 2
    $\begingroup$ BTW, the bible on such things is the book Sparsity: springer.com/us/book/9783642278747 $\endgroup$ – Sariel Har-Peled Feb 8 '18 at 5:24
  • $\begingroup$ 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? $\endgroup$ – delete000 Feb 8 '18 at 13:06
  • $\begingroup$ 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. $\endgroup$ – Sariel Har-Peled Feb 8 '18 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.