4
$\begingroup$

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.

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

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.

$\endgroup$
  • $\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 '13 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$ – David Eppstein Jun 13 '13 at 0:31
  • $\begingroup$ No. You are correct, I can't think of such a way. $\endgroup$ – SamiD Jun 13 '13 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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