There are some results on planar triangulations I was trying to generalize to a larger class of graphs.
So, what I am looking for is, a set of graphs such that the intersection of this set and the set of planar graphs is the set of planar triangulations.
Is there a ``sensible'' such set? Or any such set that is already well-known? I am somewhat new to this area of mathematics so there could be something common I am missing.
One potential set of graphs I was thinking of (let's call them `nice'), for example, is the set of graphs ``generated'' by the following:
- take a nice graph of order $n$, along with some `designated' set of triangles
- add a vertex $x$, adjacent to the vertices of exactly one designated triangle $abc$, and replace $abc$ in the set of designated triangles with $abx$, $bcx$, $cax$
with this being applied recursively, the only nice graph of order 3 being the triangle, and itself being a designated triangle
This, I believe, retains the nice property of the number of edges always being $3n-6$ when $n$ is the number of vertices, so seems a nice generalization to me. I believe it generates all the planar triangulations and no other planar graphs (please correct me if I am wrong). However, the definition is somewhat convoluted.
Another possibility I thought about is to look at graphs such that, for every cycle, for every edge in this cycle, there is a triangle containing this edge. Is this in fact equivalent? Not sure.
This is quite an open-ended question. I did look around but I didn't find any sensible class of graphs which matches my description.