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.

Improve this question
$\endgroup$
1
  • 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
    Commented Jun 12, 2013 at 0:57

1 Answer 1

Reset to default
5
$\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.

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