I think Ben Barber has the correct idea, but his exact statement is not quite right. To make $\gamma$ a Jordan curve, it is sufficient that there exist four vertices like he describes, or three vertices connected to both subsets, as in the example in the question.

Moreover, this is sufficient. Suppose neither set of vertices occurs. Then there are either $0$, $1$, or $2$ vertices connected to both subsets. If there are $0$, then there can be at most $3$ moments on the circle where you switch from vertices connected to $S_1$ to vertices connected to $S_2$ or back, so there are at most $2$ moments, so you can draw a line between them and put $S_1$ on what side and $S_2$ on the other. If there is $1$ vertex connected to both, then excluding that one there can be at most $1$ moment where you switch from vertices connected to $S_1$ to vertices connected to $S_2$ or back, so you can draw a line between that moment and the vertex connected to both and put $S_1$ on one side and $S_2$ on the other. If there are $2$ vertices connected to both, then on either side of them only one of $S_1$ and $S_2$ can occur, and neither can occur on both sides, so you can draw a line between them and put $S_1$ on one side and $S_2$ on the other.

Thus Hans Stricker's and Aaron Meyerowitz's examples are minimal in another sense - they are minimal minors.

I think Ben Barber has the correct idea, but his exact statement is not quite right. To make $\gamma$ a Jordan curve, it is sufficient that there exist four vertices like he describes, or three vertices connected to both subsets, as in the example in the question.

Moreover, this is sufficient. Suppose neither set of vertices occurs. Then there are either $0$, $1$, or $2$ vertices connected to both subsets. If there are $0$, then there can be at most $3$ moments on the circle where you switch from vertices connected to $S_1$ to vertices connected to $S_2$ or back, so there are at most $2$ moments, so you can draw a line between them and put $S_1$ on what side and $S_2$ on the other. If there is $1$ vertex connected to both, then excluding that one there can be at most $1$ moment where you switch from vertices connected to $S_1$ to vertices connected to $S_2$ or back, so you can draw a line between that moment and the vertex connected to both and put $S_1$ on one side and $S_2$ on the other. If there are $2$ vertices connected to both, then on either side of them only one of $S_1$ and $S_2$ can occur, and neither can occur on both sides, so you can draw a line between them and put $S_1$ on one side and $S_2$ on the other.

For question $2$, If a graph consists of:

• two subgraphs separated by an edge
• two subgraphs, neither a path, separated by two edges
• two subgraphs glued together on a vertex

then the whole graph contains a Jordan curve if and only if one of the subgraphs does. So we can decompose a graph until it cannot be divided in this way. If we could also decompose it into pairs of vertices, we could decompose it into $3$-connected planar pieces and apply Steinitz's theorem, but that does not seem to be quite right.