It is well known that bounded diameter planar graphs have bounded treewidth (e.g. see this). Does the converse hold? That is, is every planar bounded treewidth graph the (induced?) subgraph of a bounded diameter planar graph?

I am interested in a proof sketch/reference if this is true or a counterexample if this is false.

Note1: David's correct answer below is in the negative. In its light can we modify the question to read: Are k-outerplanar graphs subgraphs of simultaneously bounded diameter and bounded genus graphs?

Note2: David further indicates (correctly) that the nested triangles graph cannot be made bounded tree-width even at the expense of increasing the genus to a constant.

  • 2
    $\begingroup$ I'd recommend posting your followup as a separate question that references this one (since this question is essentially resolved) $\endgroup$ Jun 12, 2013 at 0:57

1 Answer 1


No: see the nested triangles graph. It has bounded treewidth (more strongly, bounded pathwidth and bandwidth) but cannot be augmented to have bounded diameter while preserving planarity.

  • $\begingroup$ A followup question: what if we replace planar by bounded genus above? I.e. k-outerplanar graphs are subgraphs of bounded diameter bounded genus graphs? $\endgroup$
    – SamiD
    Jun 12, 2013 at 0:29
  • 1
    $\begingroup$ Do you have a way of reducing the diameter of the nested triangles graph below linear by adding edges while keeping the genus bounded? $\endgroup$ Jun 13, 2013 at 0:31
  • $\begingroup$ No. You are correct, I can't think of such a way. $\endgroup$
    – SamiD
    Jun 13, 2013 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.