<p>I believe that the universal graphs for trees constructed by <a href="https://dx.doi.org/10.1112%2Fjlms%2Fs2-27.2.203">Chung and Graham 1983</a> have treewidth $\Theta(\log n)$. Or for a slightly simpler but similar example consider the transitive closures of balanced binary trees.</p>

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

CC BY-SA 3.0
2016-02-07T19:14:55.417Z
2016-02-07T19:14:55.417Z
David Eppstein
<p>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)),...</p>

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

<ol>
<li>Are there well known graph classes with treewidth $O(\log\log n)$?</li>
<li>Are there well known graph classes with treewidth $O(\log n)$?</li>
</ol>

<p>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.</p>

<p><strong>Obs:</strong> 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.</p>

CC BY-SA 3.0
2016-02-07T11:45:28.640Z
Minor free graphs (planar++) have treewidth $O(\sqrt(n))$, a lot of graph classes have booleanwidth $O(\log n)$, see this paper: http://www.ii.uib.no/~martinv/Papers/Logarithmic_booleanwidth.pdf
daniello
CC BY-SA 3.0
2016-02-07T14:21:37.923Z
@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
<graph-theory><treewidth>
Classes of graphs with superconstant treewidth
Mateus de Oliveira Oliveira
# Classes of graphs with superconstant treewidth

(Asked by: username_0 on 2016-02-07)

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.

**Tags:** graph-theory, treewidth
> **Comments:**
> **username_1**: Minor free graphs (planar++) have treewidth $O(\sqrt(n))$, a lot of graph classes have booleanwidth $O(\log n)$, see this paper: http://www.ii.uib.no/~martinv/Papers/Logarithmic_booleanwidth.pdf  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_2 on 2016-02-07. Score: 15 | Accepted answer

I believe that the universal graphs for trees constructed by [Chung and Graham 1983](https://dx.doi.org/10.1112%2Fjlms%2Fs2-27.2.203) 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).


---

