<p>Actually, the obtained subgraphs may not have bounded diameter, but they still have bounded tree-width. In order to see this, take one such subgraph $H$, and build $H'$ by adding a new vertex $u$ that is connected to each of the top-level vertices of $H$ (remember that $H$ was obtained as $k-1$ consecutive layers of a BFS tree). Then clearly $diam(H') \leq 2k$ since any vertex in $H'$ is at distance less than $k$ of $u$. We then know that $tw(H') = O(diam(H')) = O(k)$. Finally, $H$ is a minor of $H'$ so $tw(H) \leq tw(H')$, hence $tw(H) = O(k)$.</p>

CC BY-SA 3.0
2012-11-08T06:24:24.963Z
Yes, that's basically it. Instead of adding a new vertex to form $H'$, you could view it as a minor of the original graph, formed by contracting all the earlier BFS levels.
David Eppstein
CC BY-SA 3.0
2012-11-08T00:30:53.000Z
2012-11-08T00:30:53.000Z
beauby
<p>While trying to understand Baker's approach (also explained in <a href="http://arxiv.org/pdf/math.CO/9907126.pdf" rel="nofollow">this article by Eppstein</a>) to designing PTAS's for planar graphs, I came across a difficulty. </p>

<p>The idea is, given an integer $k$, decompose the graph into subgraphs of tree-width bounded by $O(k)$ (which for planar graphs happens if $diameter = O(k)$), then solve the problem on the subgraphs in polynomial-time, and finally glue the solutions together to get a polynomial-time $(1 + O(1/k))$-approx.</p>

<p>The decomposition method described in the part $8$ of <a href="http://arxiv.org/pdf/math.CO/9907126.pdf" rel="nofollow">the article</a>, amounts to, as far as I understood, pick any vertex, get a BFS tree from that vertex, and remove every $k$-th level of the tree (potentially starting at level $0 \leq i &lt; k$, but I do not think it matters for this part).</p>

<p>The author then argues that the obtained subgraphs (consisting each of at most $k-1$ levels of the BFS tree), have bounded diameter (i.e. depending only on $k$). </p>

<p>This is the part I do not understand. For instance, what happens if some layer of the tree is a long path ? How is the diameter of a subgraph containing this layer bounded ?</p>

<p>Thank you for any help,</p>

<p>Lucas</p>

CC BY-SA 3.0
2012-11-08T03:38:07.940Z
This is actually Brenda Baker's approach, not mine. The parts I did were to use it for subgraph isomorphism rather than approximation, and to extend it to any apex-minor-free graph family.
David Eppstein
CC BY-SA 3.0
2012-11-08T04:26:26.563Z
This is (obviously) right. I edited my post to clarify things. However, I found that the decomposition scheme presented in your article (or at least the way it is presented) was easier to approach than the decomposition in $k$-outerplanar graphs presented in Baker's article.
beauby
CC BY-SA 3.0
2012-11-11T06:13:48.970Z
I don't remember all the details in this approach but I could recall nor find that they claim the subgraphs have bounded diameter.
I thought it says: The graph induced by the vertices in any k consecutive layers (say i to i+k) found by a BFS has tree-width $O(k)$.
This is easily seen if one contract all the vertices in early (i.e. layers 1 to i) then the graph has bounded diameter, hence bounded tree-width.
Martin Vatshelle
<ds.algorithms><graph-theory><planar-graphs><approximation>
Understanding bounded-diameter decomposition of graphs for PTAS
beauby
# Understanding bounded-diameter decomposition of graphs for PTAS

(Asked by: username_0 on 2012-11-07)

While trying to understand Baker's approach (also explained in [this article by Eppstein](http://arxiv.org/pdf/math.CO/9907126.pdf)) to designing PTAS's for planar graphs, I came across a difficulty.

The idea is, given an integer $k$, decompose the graph into subgraphs of tree-width bounded by $O(k)$ (which for planar graphs happens if $diameter = O(k)$), then solve the problem on the subgraphs in polynomial-time, and finally glue the solutions together to get a polynomial-time $(1 + O(1/k))$-approx.

The decomposition method described in the part $8$ of [the article](http://arxiv.org/pdf/math.CO/9907126.pdf), amounts to, as far as I understood, pick any vertex, get a BFS tree from that vertex, and remove every $k$-th level of the tree (potentially starting at level $0 \leq i < k$, but I do not think it matters for this part).

The author then argues that the obtained subgraphs (consisting each of at most $k-1$ levels of the BFS tree), have bounded diameter (i.e. depending only on $k$).

This is the part I do not understand. For instance, what happens if some layer of the tree is a long path ? How is the diameter of a subgraph containing this layer bounded ?

Thank you for any help,

Lucas

**Tags:** ds.algorithms, graph-theory, planar-graphs, approximation

> **Comments:**
> **username_1**: This is actually Brenda Baker's approach, not mine. The parts I did were to use it for subgraph isomorphism rather than approximation, and to extend it to any apex-minor-free graph family.  
> **username_0**: This is (obviously) right. I edited my post to clarify things. However, I found that the decomposition scheme presented in your article (or at least the way it is presented) was easier to approach than the decomposition in $k$-outerplanar graphs presented in Baker's article.  
> **username_2**: I don't remember all the details in this approach but I could recall nor find that they claim the subgraphs have bounded diameter. I thought it says: The graph induced by the vertices in any k consecutive layers (say i to i+k) found by a BFS has tree-width $O(k)$. This is easily seen if one contract all the vertices in early (i.e. layers 1 to i) then the graph has bounded diameter, hence bounded tree-width.  

---

## 1 answers

### Answer by username_0 on 2012-11-08. Score: 5 | Accepted answer

Actually, the obtained subgraphs may not have bounded diameter, but they still have bounded tree-width. In order to see this, take one such subgraph $H$, and build $H'$ by adding a new vertex $u$ that is connected to each of the top-level vertices of $H$ (remember that $H$ was obtained as $k-1$ consecutive layers of a BFS tree). Then clearly $diam(H') \leq 2k$ since any vertex in $H'$ is at distance less than $k$ of $u$. We then know that $tw(H') = O(diam(H')) = O(k)$. Finally, $H$ is a minor of $H'$ so $tw(H) \leq tw(H')$, hence $tw(H) = O(k)$.

> **Comments:**
> **username_1**: Yes, that's basically it. Instead of adding a new vertex to form $H'$, you could view it as a minor of the original graph, formed by contracting all the earlier BFS levels.  

---

