# Classes of graphs with superconstant treewidth

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.

• 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 – daniello Feb 7 '16 at 11:45
• @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. – Mateus de Oliveira Oliveira Feb 7 '16 at 14:21

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