Suppose $S$ has a separating set $S = \{v,w\}$. Let $C$ be the smallest component of $G-S$ that doesn't have any vertices of degree $\le 2$, and assume that $S$ is chosen to make $C$ as small as possible.
This, in particular, means that each of $v$ and $w$ has at least two neighbors in $C$. If, say, $w$ has only one neighbor $w'$ in $C$, then $S' = \{v,w'\}$ is another separating set of size $2$, and one of the components of $G-S'$ is $C-\{w'\}$, which is smaller than $C$. (And $C - \{w'\}$ cannot be empty, because then $w'$ would have had degree $\le 2$.)
Also, assuming $G$ is $2$-connected, there is a path connecting $v$ and $w$ outside $C$. Let $x$ be a neighbor of $v$ outside $C$; deleting $v$ should leave a path from $x$ to $C$, which must go through $w$.
Now create a new graph $G'$ in which all vertices outside $C \cup S$ are deleted, and we add a new edge $vw$ if it did not exist already. In $G'$, $v$ and $w$ still have degree at least $3$, and the degrees in $C$ are unchanged.
By induction, $G'$ contains a subdivision of $K_4$. This can be turned into a subdivision of $K_4$ in $G$: if the edge $vw$ is needed and not present in $G$, we can replace it by a path from $v$ to $w$ outside $C$, which we know exists.
Alternatively, if you're willing to use some powerful classification results similar to your observation about planar graphs, then you can start from the fact that the graphs with no subdivision of $K_4$ are precisely the series-parallel graphs.
A series-parallel graph must have a vertex of degree $2$. More precisely, a series-parallel graph with source $s$ and sink $t$ either has no other vertices, or else has a vertex of degree $2$ other than $s$ and $t$. To prove this, you can verify that this property is preserved under both series composition and parallel composition:
- A series composition of two $K_2$s results in a path on $3$ vertices, which creates a vertex of degree $2$ other than $s$ and $t$. A parallel composition of two $K_2$s creates a multigraph, so it's not allowed.
- In a series or parallel composition of two graphs, at least one of which has three or more vertices, one of the graphs already had a vertex of degree $2$ other than $s$ and $t$. That vertex still has degree $2$ after the composition.
Therefore a graph with minimum degree $3$ cannot be series-parallel, so it has a subdivision of $K_4$.
We can refine this argument to also rule out graphs in which only one vertex has degree less than $2$. If our series and parallel composition involved at least two graphs with three or more vertices at any point, then each of them had an internal vertex of degree $2$. If not, then $s$ and $t$ can each have degree at most $2$: their degrees increase only with parallel compositions, and we can't parallel-compose a $2$-vertex graph with itself, so for $s$ or $t$ to reach degree $3$, we'd need two larger graphs.
I know it has a bit of irony that I found a way to solve it just after putting the bounty. I had proven before that every $3-$connected nonplanar graph contains a $K_{3,3}-$minor, but hadn't really realized that it also has a $K_{3,3}-$subdivision (In my proof there was a part when I couldn't find such subdivision but I still was able to get a minor so since that's what I wanted to find I didn't worry about that; now, after verifying that part, I see that such subdivision can be easily found given what I already had).
So, I can use the proof of the lemma 3.4 here.
In this case I can find a subdivision of $K_{3,3}$ in any $3-$connected nonplanar graph, in particular one built by adding an edge to a maximal planar graph.
Best Answer
I know this isn't exactly what you asked for, but there's another, easier way to prove the graph is non-planar, based on Tutte's conflict graph theorem. Because the graph has a Hamilton cycle, it's easy to tell whether or not it's planar. Let's redraw the graph:
To attempt to embed the graph in the plane, we can start by placing the graph nodes at the vertices of a regular polygon, in the order of the cycle, and represent the remaining edges as diagonals. Consider the diagonals of the polygon. If two of them intersect when they are both drawn inside the polygon, then they will also intersect if both are drawn (as graph edges) outside the polygon. Now look at the three diagonals colored red. Each intersects both the others, so at least two must be drawn inside or at least two must be drawn outside, and there is no planar embedding.
The conflict graph is the graph whose vertices are the diagonals, in which two vertices are adjacent if the two diagonals intersect when drawn in the same region. A graph with a Hamilton cycle is planar if and only if the conflict graph is bipartite.
(I had to change the labelling of the vertices, because Geogebra won't accept a number as the label of a point.)