11
$\begingroup$

There are several interesting classes of graphs with bounded treewidth. For instance, trees (treewidth 1), series parallel graphs (treewidth 2), outerplanar graphs (treewidth 2), $k$-outerplanar graphs (treewidth O(k)), graphs of branchwidth $k$ (treewidth O(k)),...

Question: Are there examples of interesting classes of graphs whose treewidth is not bounded by a constant, but by a low-growing function?

  1. Are there well known graph classes with treewidth $O(\log\log n)$?
  2. Are there well known graph classes with treewidth $O(\log n)$?

I would also be interested in classes of graphs with treewidth $O(\log^k n)$ or $O(\log\log...n)$ where the logarithm is repeated a constant number of times.

Obs: Of course it is easy to cook up artificial families of graphs with a given treewidth, like the family of $\;O(\log n)\times n\;$ grids. So I'm primarily looking for family of graphs which have been studied in other branches of graph theory and which happen to have treewidth $O(\log n)$ or $O(\log\log n)$, but non-constant treewidth.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Minor free graphs (planar++) have treewidth $O(\sqrt(n))$, a lot of graph classes have booleanwidth $O(\log n)$, see this paper: ii.uib.no/~martinv/Papers/Logarithmic_booleanwidth.pdf $\endgroup$
    – daniello
    Feb 7, 2016 at 11:45
  • $\begingroup$ @daniello Thank you very much for your comment. $\sqrt{n}$ is still too big. I'm really interested in treewidth at most polylogarithmic. The paper on boolean width is very interesting and gives several nice classes with boolean width $O(\log n)$. But since boolean width is at most cliquewidth squared, there are graphs of constant boolean width and $\sqrt{n}$ treewidth. So the results in the paper do not translate immediately to treewidth. $\endgroup$
    – Mateus de Oliveira Oliveira
    Feb 7, 2016 at 14:21

1 Answer 1

Reset to default
15
$\begingroup$

I believe that the universal graphs for trees constructed by Chung and Graham 1983 have treewidth $\Theta(\log n)$. Or for a slightly simpler but similar example consider the transitive closures of balanced binary trees.

However, there's a negative result here, too. All the examples you give of interesting graph families are minor-closed, or very closely related to minor-closed families. But a minor-closed graph family either contains all planar graphs (and hence has maximum treewidth $\Theta(\sqrt n)$) or has a forbidden planar minor (and hence has bounded treewidth).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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