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

<p>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. <a href="https://arxiv.org/abs/cs/0604080" rel="noreferrer">https://arxiv.org/abs/cs/0604080</a></p>

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

CC BY-SA 3.0
2017-09-13T14:41:56.283Z
2017-09-13T14:41:56.283Z
Serge Gaspers
<p>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 &gt; 0$. See Section 2 in:</p>

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

<p>Basically, they prove something much stronger: large vertex expansion is <em>the only</em> 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).</p>

CC BY-SA 4.0
2024-01-09T02:18:36.263Z
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
CC BY-SA 3.0
2017-09-13T08:00:03.123Z
2017-09-13T08:48:50.390Z
2017-09-13T08:48:50.390Z
PsySp
<p>What is the maximum treewidth of a graph with $m$ edges? In other 
words, what is the correct growth for the following function? </p>

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

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

<p>Is this also the maximum? </p>

CC BY-SA 3.0
2017-09-12T12:38:10.340Z
cubic expanders have linear treewidth.
PsySp
CC BY-SA 3.0
2017-09-12T22:31:00.863Z
@PsySp Could you please post this as an answer with a reference to the fact that expanders have linear treewidth?
Springberg
CC BY-SA 4.0
2024-01-24T10:43:41.990Z
PS: asked the question about small $m$ here: https://cstheory.stackexchange.com/questions/53806/what-is-the-smallest-graph-of-treewidth-k-having-less-edges-than-the-k1-cli
Antoine Amarilli 'a3nm'
<reference-request><parameterized-complexity><treewidth>
Maximum Treewidth of a Graph with $m$ Edges
Springberg
# Maximum Treewidth of a Graph with $m$ Edges

(Asked by: username_0 on 2017-09-12)

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?

**Tags:** reference-request, parameterized-complexity, treewidth

> **Comments:**
> **username_1**: cubic expanders have linear treewidth.  
> **username_0**: @username_1 Could you please post this as an answer with a reference to the fact that expanders have linear treewidth?  
> **username_2**: PS: asked the question about small $m$ here: https://cstheory.stackexchange.com/questions/53806/what-is-the-smallest-graph-of-treewidth-k-having-less-edges-than-the-k1-cli  

---

## 2 answers

### Answer by username_1 on 2017-09-13. Score: 11 | Accepted answer

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

> **Comments:**
> **username_4**: 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$?  

---

### Answer by username_3 on 2017-09-13. Score: 7

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.


---

