While trying to understand Baker's approach (also explained in this article by Eppstein) 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, 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,


  • 2
    $\begingroup$ 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. $\endgroup$ Commented Nov 8, 2012 at 3:38
  • 1
    $\begingroup$ 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. $\endgroup$
    – beauby
    Commented Nov 8, 2012 at 4:26
  • $\begingroup$ 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. $\endgroup$ Commented Nov 11, 2012 at 6:13

1 Answer 1


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)$.

  • 2
    $\begingroup$ 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. $\endgroup$ Commented Nov 8, 2012 at 6:24

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.