How sparse is a graph of bounded treewidth?

Question

I often see references to treewidth being a measure of sparseness, but is there a known bound? More exactly, given a graph $G$ with $n$ vertices and treewidth at most $k$, is there a function of $n$ and $k$ which bounds the possible number of edges in $G$?

Answer 1

The maximal graphs with treewidth $k$ are the $k$-trees which are constructed by starting with a $(k+1)$-clique and iteratively adding vertices of degree $k$ such that its neighbors form a $k$-clique.

The total number of edges in a $k$-tree with $n$ vertices is $\binom{k+1}{2} + k(n - k - 1)$ which is found by counting the edges in the $(k+1)$-clique and the edges incident to the $n-k-1$ vertices iteratively added to the $k$-tree. Since any graph $G$ with treewidth $k$ is a subgraph of a $k$-tree this is an upper bound on $|E(G)|$.