Jordan-like cycles in graphs

Question

[Added another complementary question below.]

Motivation

The 1-skeleton of the triangular bipyramid seems to be the smallest connected planar graph $G$ with the following

Property: There is a cycle $\gamma$ ($\color{red}{\mathsf{red}}$) in $G$ with exactly two connected components $G_1, G_2$ of $G - \gamma$ such that for every graph embedding $\pi$ of $G$ into the plane $\mathbb{R}^2$ the component $G_1$ ($\color{blue}{\mathsf{blue}}$) is contained in the interior of $\pi(\gamma)$ and the other component $G_2$ ($\color{black}{\mathsf{black}}$) is contained in the exterior of $\pi(\gamma)$ – or vice versa.

Definition: A cycle $\gamma$ in the graph $G$ is a Jordan cycle if $G - \gamma$ splits up into exactly two connected components $G_1, G_2$ such that for every graph embedding $\pi$ of $G$ into the plane $\mathbb{R}^2$ the component $G_1$ is contained in the interior of $\pi(\gamma)$ and the other component $G_2$ is contained in the exterior of $\pi(\gamma)$ – or vice versa.

Questions

1. (How) can the property of being a Jordan cycle $\gamma$ be defined purely combinatorial, without mentioning graph embeddings $\pi$ and Jordan curves $\pi(\gamma)$?

2. (How) can planar graphs containing a Jordan cycle be characterized purely combinatorially?

3. ADDED: Can planar graphs be characterized in which every cycle is a Jordan cycle?

Answer 1

The following is an answer to question 1. You get a free, if not very illuminating, answer to question 2 by examining each cycle of $G$ in turn.

We say that two subsets $S_1$ and $S_2$ of $\gamma$ cross if there are distinct vertices $x_1$, $x_2$, $y_1$ and $y_2$, in that cyclic order around $\gamma$, such that $x_i, y_i \in S_i$. If $S_1$ and $S_2$ do not cross then there are vertices $u$ and $v$ of $\gamma$ such that $S_1$ lies between $u$ and $v$, and $S_2$ lies between $v$ and $u$ (where each arc is traversed in the same cyclic direction).

Let $G_1$ and $G_2$ be adjacent to subsets $S_1$ and $S_2$ respectively of the vertices of $\gamma$. We claim that $\gamma$ is Jordan if and only if $S_1$ and $S_2$ cross.

If $S_1$ and $S_2$ cross, then let $x_1$, $x_2$, $y_1$ and $y_2$ be as in the definition of crossing. Since the $G_i$ are connected, there is a path in $G$ from $x_1$ to $y_1$ and from $x_2$ to $y_2$. But in any planar drawing of $G$ one of these paths must be drawn inside $\gamma$, and the other must be drawn outside (else the paths would cross).

If $S_1$ and $S_2$ do not cross, then $G_1$ and $G_2$ attach to (almost) disjoint arcs of $\gamma$. Then, in any drawing of $G$, their drawings can be rotated freely around $\gamma$ in $\mathbb{R}^3$; in particular, they can both be laid down inside $\gamma$ in $\mathbb{R}^2$.

Answer 2

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.