## 2 Preliminaries  
A graph \(G\) consists of a set \(V(G)\) of vertices and a set \(E(G)\) of edges, where each edge \(e\) of \(E(G)\) is a subset of two elements from \(V(G)\). For edge \(e=\{u,v\}\in E(G)\), we say that vertices \(u\) and \(v\) are adjacent. The node degree of a vertex \(u\) is the number of vertices adjacent to \(u\). Vertex \(u\) is dominated by vertex \(v\) if \(u\) and \(v\) are adjacent or \(u=v\). Vertex \(u\) is dominated by a set \(D\) if \(u\) is dominated by a vertex of \(D\). Edge \(e\) is covered by a vertex \(u\) if \(u\in e\). For a subset \(U\subseteq V(G)\) and a subset \(A\subseteq E(G)\), we denote by \(G[U]\) and \(G[A]\) the subgraphs of \(G\) induced by \(U\) and \(A\), respectively. For a subset \(A\subseteq E(G)\), we denote by \(E(G)\setminus A\) by \(\overline{A}\) when \(G\) is clear from the context. A separation of graph \(G\) is a pair \((A,\overline{A})\) of subsets of \(E(G)\). For each \(A\subseteq E(G)\), we denote by \(\partial(A)\) the vertex set \(V(A)\cap V(\overline{A})\). The _order_ of separation \((A,\overline{A})\) is \(|\partial(A)|=|\partial(\overline{A})|\). A graph \(G\) is planar if \(G\) has a planar embedding (a draw on a sphere without edge crossing). We call a planar embedding of \(G\) a plane graph. A face of a plane graph \(G\) is a connected region of the sphere bounded by edges and vertices of \(G\) and containing no edge or vertex of \(G\) in its interior. For a plane graph \(G\) and a face \(f\) of \(G\), let \(V_{G}(f)\) be the set of vertices in \(V(G)\) incident to \(f\). Given a plane graph \(G\) and a face \(f_{o}\) (called outer face) of \(G\), let \(V_{1}=V_{G}(f_{o})\). For \(i\geq 1\), let \(U_{i}=\cup_{j=1}^{i}V_{j}\), \(G_{i}=G[V(G)\setminus U_{i}]\), \(f_{i}\) be the face of \(G_{i}\) such that \(f_{o}\subseteq f_{i}\), and \(V_{i+1}=V_{G_{i}}(f_{i})\). We call the vertices of \(V_{i}\)_level_\(i\) vertices of \(G\). Intuitively, \(G_{i}\) is the plane graph obtained from removing vertices of levels \(1,2,...,i\) from \(G\). \(V_{i+1}\) is the vertices of \(G_{i}\) incident to the outer face of \(G_{i}\). Branch-decomposition based algorithms play a central role in the PTAS studied in this paper. The notion of branch-decomposition is introduced by [PERSON] and [PERSON] [16]. A _branch-decomposition_ of graph \(G\) is a pair \((\phi,T)\) where \(T\) is a tree each internal node of which has degree 3 and \(\phi\) is a bijection from the set of leaves of \(T\) to \(E(G)\). Consider a link \(e\) of \(T\) and let \(L_{1}\) and \(L_{2}\) denote the sets of leaves of \(T\) in the two respective subtrees of \(T\) obtained by removing \(e\). We say that the separation \((\phi(L_{1}),\phi(L_{2}))\) is induced by this link \(e\) of \(T\). We define the width of the branch-decomposition \((\phi,T)\) to be the largest order of the separations induced by links of \(T\). The _branchwidth_ of \(G\), denoted by \(\mathrm{bw}(G)\), is the minimum width of all branch-decompositions of \(G\). In the rest of this paper, we identify a branch-decomposition \((\phi,T)\) with the tree \(T\), regarding each leaf of \(T\) as an edge of \(G\). Given a branch-decomposition \(T\) of \(G\), an optimization problem \(P\) in \(G\) may be solved by the dynamic programming method as follows: convert \(T\) into a rooted binary tree by replacing a link \(\{x,y\}\) of \(T\) with three links \(\{x,z\},\{y,z\},\{z,r\}\), where \(z\) and \(r\) are new nodes to \(T\), and \(r\) is the root of \(T\). For a link \(e=\{u,v\}\) of \(T\), assume \(u\) is the end node reachable from root \(r\) by passing through \(e\). Let \(A_{e}\) be the set of leaves of \(T\) reachable from \(r\) by passing through \(e\). Link \(e=\{u,v\}\) is called a leaf link if \(u\) is a leaf node, otherwise an internal link. An internal link \(e\) has two child links \(e_{1}\) and \(e_{2}\) covered by \(u\). Notice that \(A_{e}=A_{e_{1}}\cup A_{e_{2}}\). For a leaf link \(e\), all partial solutions of \(P\) in the subgraph \(G[A_{e}]\) can be computed by enumeration.