<p>No: see the <a href="http://en.wikipedia.org/wiki/Nested_triangles_graph" rel="noreferrer">nested triangles graph</a>. It has bounded treewidth (more strongly, bounded pathwidth and bandwidth) but cannot be augmented to have bounded diameter while preserving planarity.</p>

CC BY-SA 3.0
2013-06-12T00:29:39.483Z
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?
SamiD
CC BY-SA 3.0
2013-06-13T00:31:11.927Z
Do you have a way of reducing the diameter of the nested triangles graph below linear by adding edges while keeping the genus bounded?
David Eppstein
CC BY-SA 3.0
2013-06-13T11:07:30.520Z
No. You are correct, I can't think of such a way.
SamiD
CC BY-SA 3.0
2013-06-12T00:15:26.907Z
2013-06-12T00:15:26.907Z
David Eppstein
<p>It is well known that bounded diameter planar graphs have bounded treewidth (e.g. see <a href="http://igitur-archive.library.uu.nl/math/2006-1214-201709/bodlaender_88_planar_graphs.pdf" rel="nofollow">this</a>). Does the converse hold? That is, is every planar bounded treewidth graph the (induced?) subgraph of a bounded diameter planar graph? </p>

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

<p>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?</p>

<p>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. </p>

CC BY-SA 3.0
2013-06-12T00:57:09.560Z
I'd recommend posting your followup as a separate question that references this one (since this question is essentially resolved)
Suresh Venkat
<reference-request><graph-theory>
k-outerplanar graphs are subgraphs of bounded diameter planar graphs? of bounded diameter bounded genus graphs?
SamiD
# k-outerplanar graphs are subgraphs of bounded diameter planar graphs? of bounded diameter bounded genus graphs?

(Asked by: username_0 on 2013-06-11)

It is well known that bounded diameter planar graphs have bounded treewidth (e.g. see [this](http://igitur-archive.library.uu.nl/math/2006-1214-201709/bodlaender_88_planar_graphs.pdf)). 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.

**Tags:** reference-request, graph-theory

> **Comments:**
> **username_1**: I'd recommend posting your followup as a separate question that references this one (since this question is essentially resolved)  

---

## 1 answers

### Answer by username_2 on 2013-06-12. Score: 5 | Accepted answer

No: see the [nested triangles graph](http://en.wikipedia.org/wiki/Nested_triangles_graph). It has bounded treewidth (more strongly, bounded pathwidth and bandwidth) but cannot be augmented to have bounded diameter while preserving planarity.

> **Comments:**
> **username_0**: 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?  
> **username_2**: Do you have a way of reducing the diameter of the nested triangles graph below linear by adding edges while keeping the genus bounded?  
> **username_0**: No. You are correct, I can't think of such a way.  

---

