Algorithm

INDEPENDENT-SET(${\displaystyle G}$, ${\displaystyle w}$, ${\displaystyle \epsilon }$)
    Choose an arbitrary vertex ${\displaystyle r}$
    ${\displaystyle k=1/\epsilon }$
    find the breadth-first search levels for ${\displaystyle G}$ rooted at ${\displaystyle r}$ ${\displaystyle {\pmod {k}}}$: ${\displaystyle \{V_{0},V_{1},\ldots ,V_{k-1}\}}$

    for ${\displaystyle \ell =0,\ldots ,k-1}$
        find the components ${\displaystyle G_{1}^{\ell },G_{2}^{\ell },\ldots ,}$ of ${\displaystyle G}$ after deleting ${\displaystyle V_{\ell }}$

    for ${\displaystyle i=1,2,\ldots }$
       compute ${\displaystyle S_{i}^{\ell }}$, the maximum-weight independent set of ${\displaystyle G_{i}^{\ell }}$

    ${\displaystyle S^{\ell }=\cup _{i}S_{i}^{\ell }}$
    let ${\displaystyle S^{\ell ^{*}}}$ be the solution of maximum weight among ${\displaystyle \{S^{0},S^{1},\ldots ,S^{k-1}\}}$

    return ${\displaystyle S^{\ell ^{*}}}$

Notice that the above algorithm is feasible because each ${\displaystyle S^{\ell }}$ is the union of disjoint independent sets.

Dynamic programming

Dynamic programming is used when we compute the maximum-weight independent set for each ${\displaystyle G_{i}^{\ell }}$. This dynamic program works because each ${\displaystyle G_{i}^{\ell }}$ is a ${\displaystyle k}$-outerplanar graph. Many NP-complete problems can be solved with dynamic programming on ${\displaystyle k}$-outerplanar graphs. Baker's technique can be interpreted as covering the given planar graphs with subgraphs of this type, finding the solution to each subgraph using dynamic programming, and gluing the solutions together.