The approach you're taking is much more complicated than the easiest approach to generating the graphs counted by A000109. So if you don't mind, I'll give you an easy-to-implement way to generate those graphs, rather than an easy-to-implement way to check for planarity (which I'm not sure exists, even in the case where we're just adding one edge to a planar graph).
In the paper Fast generation of planar graphs (G. Brinkmann and Brendan McKay), Figure 4 and the example at the bottom of page 4 together give an easy-to-implement way to eventually generate all planar triangulations on at least $4$ vertices. Here's a summary of how it works.
We define the following three operations that turn an $n$-vertex planar triangulation into an $(n+1)$-vertex one:
- Pick a $3$-cycle in the graph and add a new vertex adjacent to all its vertices.
- Pick two adjacent $3$-cycles in the graph (sharing an edge). Delete their common edge to make a $4$-cycle and add a new vertex adjacent to all its vertices.
- Pick three $3$-cycles $C_1, C_2, C_3$ such that $C_1$ and $C_2$ share an edge and $C_2$ and $C_3$ share a different edge. Delete their common edge to make a $5$-cycle and add a new vertex adjacent to all its vertices.
The claim in the paper is that, if you start from all the $n$-vertex planar triangulations and just apply these operations to all of them in all possible ways, you get all the $(n+1)$-vertex planar triangulations. This is probably easier to implement than any test for planarity.
(You might want to look into doubly connected edge lists (DCELs) or some similar data structure for storing the planar graphs you're working with.)
You will get a lot of redundancy in your list of $(n+1)$-vertex planar triangulations. So you'll have to somehow check when two planar triangulations are isomorphic, and delete the redundant ones. But this is also easy to do if you don't mind inefficiency: for one thing, we could just check all possible bijections between the vertex sets. (A lot of the complexity in Brinkmann and McKay's actual algorithms is about dealing with this redundancy more efficiently.)