## 2 Preliminaries
For an internal link \(e\), assume that all partial solutions of \(P\) in the subgraph \(G[A_{e_{1}}]\) and those in \(G[A_{e_{2}}]\) have been computed. Then all partial solutions of \(P\) in the subgraph \(G[A_{e}]\) are computed by merging the partial solutions in \(G[A_{e_{1}}]\) and those in \(G[A_{e_{2}}]\). The merging process is performed in a bottom-up way, from each leaf link to the link \(\{z,r\}\), to find an optimal solution of \(P\) in \(G\). The FT algorithm is a branch-decomposition-based algorithm for the planar dominating set problem. In FT Algorithm, the number of partial solutions in \(G[A_{e}]\) is \(3^{|\partial(A_{e})|}\). To compute a partial solution in \(G[A_{e}]\), every pair \((s_{1},s_{2})\) is checked, where \(s_{1}\) and \(s_{2}\) are partial solutions in \(G[A_{e_{1}}]\) and \(G[A_{e_{2}}]\), respectively. Notice that each of \(|\partial(A_{e})|,|\partial(A_{e_{1}})|,|\partial(A_{e_{2}})|\) is at most the width of the given branch-  
be a minimum dominating set of \(G[U(i,s)]\). Then \(D(i,s)\) may not be a dominating set of \(G[U(i,s)]\) and \(|S(i,s)|\leq|D(i,s)|\) may not hold. Below we show by an example that the approximation ratio of the mentioned application of [PERSON]'s framework is not bounded by any constant for the planar dominating set problem. Let \(G\) be a plane graph with 4 levels of vertices shown in Figure 1. Let \(X_{i}\) be the set of vertices of \(G\) with labels \((i,1),...,(i,x)\), \(1\leq i\leq 6\). The subgraph \(G[X_{i}]\) is a chain and there is a unique vertex in \(G\) dominating all vertices of \(X_{i}\). For a large \(x\), \(G\) has a unique minimum dominating set \(D\) with its six vertices shown as black squares in the figure. Let \(k=2\). For \(s=2\), the subgraphs \(G[U(0,2)]\) and \(G[U(1,2)]\) are shown in Figure 2 (a) and (b), respectively. Let \(D(0,2)=D\cap U(0,2)\). Then \(D(0,2)\) (the set of vertices denoted by black squares) is not a dominating set of \(G[U(0,2)]\). On the other hand, a minimum dominating set \(S(0,2)\) of \(G[U(0,2)]\) contains a fraction of vertices in \(X_{3}\) and \(|S(0,2)|>|D(0,2)|\) for large \(x=|X_{3}|\). Similarly, a minimum dominating set \(S(1,2)\) of \(G[U(1,2)]\) contains a fraction of vertices in \(X_{2}\) and \(|S(1,2)|>|D(1,2)|\). Let \(S_{2}=S(0,2)\cup S(1,2)\). Then \(|S_{2}|/|D|\) is not bounded by any constant for non-constant \(x\). Figure 1: A plane graph \(G\) with four levels of vertices. * Compute subgraphs \(G[W(i,s)]\) for \(i=0,1,...,r\). * For subgraph \(G[W(0,s)]\), find a minimum subset \(S(0,s)\) of \(W(0,s)\) that dominates every vertex of \(\cup_{j=1}^{s-1}V_{j}\) (every interior vertex). For every subgraph \(G[W(i,s)]\), \(i=1,...,r-1\), find a minimum subset \(S(i,s)\) of \(W(i,s)\) that dominates every vertex of \(\cup_{j=(i-1)\times k+s}^{i\times k+s-1}V_{j}\) (every interior vertex). For subgraph \(G[W(r,s)]\), find a minimum subset \(S(r,s)\) of \(W(r,s)\) that dominates every vertex of \(\cup_{j=(r-1)\times k+s}^{m}V_{j}\) (every interior vertex). * Let \(S_{s}=\cup_{i=0}^{r}S(i,s)\). * Let \(S\) be a set of \(S_{2},...,S_{k+1}\) with the minimum cardinality. **Theorem 3.1**: _The modified application of [PERSON]'s framework gives an \(O(2^{(6\log_{4}3)(k+2)}kn)\) time \((1+2/k)\)-approximation algorithm for the planar dominating set problem._  
**Proof:** We first show the approximation ratio of the framework. Notice that \(S_{s}=\cup_{i=0}^{r}S(i,s)\) dominates every vertex of  
\[(\cup_{j=1}^{s-1}V_{j})\cup[\cup_{i=1}^{r-1}(\cup_{j=(i-1)\times k+s}^{i\times k +s-1}V_{j})]\cup(\cup_{j=(r-1)\times k+s}^{m}V_{j})=\cup_{j=1}^{m}V_{j}=V(G)\]  
that is, \(S_{s}\) is a dominating set of \(G\). Let \(D\) be a minimum dominating set of \(G\) and let \(D(i,s)=D\cap W(i,s)\), \(s=2,...,k+1\) and \(0\leq i\leq r\). Since no vertex of \(G\) in \(V(G)\setminus W(i,s)\) can dominate any interior vertex of \(G[W(i,s)]\) and \(D\) dominates every vertex of \(G\), \(D(i,s)\) dominates every interior vertex of \(G[W(i,s)]\).