Let G be a tree on 2n vertices. The treewidth of G, tw(G) = 1. Now suppose we add n edges to G to get a graph H. An easy upper bound on tw(H) is n + 1. Is this essentially the best possible? It seems somehow that tw(H) should be O(sqrt(n)) , but this is just a vague hunch. Do we know better upper bounds than O(n) for the treewidth of a graph obtained by adding n edges to a tree on 2n vertices?
How large a treewidth can a tree plus half the edges have?
upper bounds;treewidth
Your model is not really any less general than asking about arbitrary 3-regular graphs, and 3-regular expander graphs have linear treewidth. So I don't know about constant factors, but (n) is best possible, yes.