In theoretical computer science, Baker's technique is a method for designing polynomial-time approximation schemes (PTASs) for problems on planar graphs.
It is named after Brenda Baker, who announced it in a 1983 conference and published it in the Journal of the ACM in 1994.
The bidimensionality theory of Erik Demaine, Fedor Fomin, Hajiaghayi, and Dimitrios Thilikos and its offshoot simplifying decompositions (Demaine, Hajiaghayi & Kawarabayashi (2005),Demaine, Hajiaghayi & Kawarabayashi (2011)) generalizes and greatly expands the applicability of Baker's technique for a vast set of problems on planar graphs and more generally graphs excluding a fixed minor, such as bounded genus graphs, as well as to other classes of graphs not closed under taking minors such as the 1-planar graphs.
The example that we will use to demonstrate Baker's technique is the maximum weight independent set problem.
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.