# Maximum Treewidth of a Graph with $m$ Edges

What is the maximum treewidth of a graph with $m$ edges? In other words, what is the correct growth for the following function?

$\alpha(m) = max\{\mathrm{treewidth}(G): G \mbox{ has$m$edges}\}$.

Clearly $\alpha(m) = \Omega(\sqrt{m})$, which is attained by cliques with $\Omega(\sqrt{m})$ vertices and by by $\Omega(\sqrt{m})\times \Omega(\sqrt{m})$ grids.

Is this also the maximum?

• cubic expanders have linear treewidth. Commented Sep 12, 2017 at 12:38
• @PsySp Could you please post this as an answer with a reference to the fact that expanders have linear treewidth? Commented Sep 12, 2017 at 22:31
• PS: asked the question about small $m$ here: cstheory.stackexchange.com/questions/53806/…
– a3nm
Commented Jan 24 at 10:43

There are bounded degree (in fact even cubic i.e. 3-regular) expanders on $m$ vertices with treewidth at least $\epsilon \cdot m$, for some constant $\epsilon > 0$. See Section 2 in:

Martin Grohe, Dániel Marx: On tree width, bramble size, and expansion. J. Comb. Theory, Ser. B 99(1): 218-228 (2009)

Basically, they prove something much stronger: large vertex expansion is the only reason on why the treewidth can be as much as linear (in the number of vertices, but bounded degree graphs have linear number of edges).

• Regarding your statement, 'There are bounded degree (in fact even cubic i.e., 3-regular) expanders on ( m ) vertices with treewidth at least $\epsilon \cdot m$,' are you implying that there exist certain bounded degree expander graphs whose treewidth is linear in $m$, or are you asserting that the treewidth of all bounded degree expander graphs is linear in $m$?
– Jxb
Commented Jan 9 at 2:18

The best known upper bound of the treewidth in terms of the number of edges of a graph is as follows: the pathwidth (and therefore also the treewidth) of any graph on $n$ vertices and $m$ edges is at most $13 m / 75 + o(n)$.

Alexander D. Scott and Gregory B. Sorkin. Linear-programming design and analysis of fast algorithms for Max 2-CSP, Discrete Optimization 4 (2007), no. 3-4, 260-287. https://arxiv.org/abs/cs/0604080

Joachim Kneis, Daniel Mölle, Stefan Richter, and Peter Rossmanith, A bound on the pathwidth of sparse graphs with applications to exact algorithms, SIAM Journal on Discrete Mathematics 23 (2009), no. 1, 407-427.