In the general case finding a Maximum Independent Subset of a Graph is NP-Hard.However consider the following subset of graphs:Create an $N \times N$ grid of unit square cells.Build a graph $G$ by creating a vertex corresponding to every cell.  Notice that there are $N^2$ vertices.Create an edge between two vertices if their cells share a side.  Notice there are $2N(N-1)$ edges.A Maximum Independent Subset of $G$ is obviously a checker pattern.  A cell at the $R$th row and $C$th column is part of it if $R+C$ is odd.Now we create a graph $G'$ by copying $G$ and removing some vertices and edges.  (If you remove a vertex also remove all edges it ended of course. Also note you can remove an edge without removing one of the vertices it ends.)By what algorithm can we find a Maximum Independent Subset of $G'$?
Maximum Independent Subset of 2D Grid Subgraph
algorithms;graph theory
As JeffE mentions in a comment, a grid graph is an example of a bipartite graph. If you take a bipartite graph, and remove some of the vertices, it will still be a bipartite graph.Knigs Theorem states, that for bipartite graphs, the number of vertices in a minimum covering, equals the number of edges in a maximum matching.As mentioned in the answer for Maximum Independent Set of a Bipartite Graph:The complement of a maximum independent set is a minimum vertex  coverWhat you are asking, is how to find a maximum independent set in a grid graph with some vertices removed, and the way to do that, is to use some of the algorithms for finding a maximum matching in a bipartite graph, from that construct a minimum vertex cover, and then invert it to get a maximum independent set.The figure below shows a bipartite graph with a maximum matching (in blue), a minimum vertex cover (in red) and consequently also a maximum independent set (in white):