Consider a $5$-regular undirected planar graph with $n$ vertices (a $k$-regular graph has exactly $k$ edges emanating from every node.)
Let us say we apply an arbitrary sequence (of length $\text{poly}(n)$ for some polynomial in $n$) of the following two transformations on this graph on whatever vertices we choose.
Vertex deletion: we delete a vertex, and all edges which have that vertex as an end point.
Neighborhood flip (also called local complementation): consider the set of all neighbors $N$ of some vertex $v$ (a neighbor is a vertex $u$ such that $(u, v)$ is an edge.) For all pairs of vertices in $N$, if any two vertices in $N$ are already connected by an edge, delete that edge. Else, connect the vertices.
Does there exist a $5$-regular undirected planar graph such we reach the $k \times k$ $2$D grid graph from it, using the above two transformations, for some $k \geq \Omega(n)$?
I did some trial and error and found no such example.
The problem is, the grid graph is planar, but the neighborhood flip operation does not necessarily preserve planarity. Additionally, it does not seem to be possible to reach the grid graph just by vertex deletion.
What might be a mathematical proof that there is no such example?
Note that if we are allowed to start from a non-planar $5$-regular graph, there are many examples such that we reach the grid in the end.
For simplicity, in case it helps, you may assume we are starting from a simple graph.
Best Answer
There are $5$-regular graphs with $O(k^2)$ vertices from which we can reach the $k \times k$ grid graph using only vertex deletion.
The grid graph has $k^2$ vertices and $2k(k-1)$ edges; to make it $5$-regular by adding edges (I know that's not what you want, but bear with me) we would need to add $\frac12 k^2 + 2k$ edges. I will assume $k$ is even so that this is an integer.
If we are okay with getting a planar multigraph at the end, then this is straightforward. In the $(k-2) \times (k-2)$ interior, double the edges of a perfect matching: now all the interior vertices go up from degree $4$ to $5$. Add a loop at every boundary vertex: now the sides go up from degree $3$ to $5$, and the corners from degree $2$ to $4$. Finally, add two edges that go between the corners.
Now, replace every edge $xy$ we added by the following gadget: an icosahedral graph (a planar $5$-regular graph with $12$ vertices) in which an edge $vw$ is deleted and replaced by edges $vx$, $wy$. Replace every loop at a vertex $x$ by a similar gadget, but with edge $vw$ deleted and replaced by edges $vx, wx$.
The result is a $5$-regular planar graph with $12 \left(\frac12k^2 + 2k\right)$ extra vertices on top of the vertices in the grid graph. In other words, it's a $5$-regular planar graph with $7k^2+24k$ vertices from which we can delete $6k^2+24k$ vertices and get a $k \times k$ grid graph.