Skip to main content
Correct and clarify
Source Link
Ben Barber
  • 4.7k
  • 2
  • 27
  • 39

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$. The condition for We claim that $\gamma$ to be a Jordan cycle is thatJordan if and only if $S_1$ and $S_2$ should not cross: that is, there should be two arcs of $\gamma$, disjoint except possibly at endpoints, each of which contains one of the $S_i$.

If this condition is satisfied then any planar drawing of $G$ with one component inside$S_1$ and one component outside can be turned into a planar drawing with both components inside by reflecting the outside component in $\gamma$. If the condition is not satisfied then, since the components are connected$S_2$ cross, there are distinct verticesthen let $x_1$, $x_2$, $y_1$ and $y_2$, appearing in that cyclic order be as in the definition of crossing. Since the $\gamma$$G_i$ are connected, such thatthere is a path in $G$ from $x_1$ andto $y_1$ are joined by a pathand from $x_2$ to $y_2$. But in any planar drawing of $G_1$$G$ one of these paths must be drawn inside $\gamma$, and the other must be drawn outside $x_2$(else the paths would cross).

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

Let $G_1$ and $G_2$ be adjacent to subsets $S_1$ and $S_2$ respectively of the vertices of $\gamma$. The condition for $\gamma$ to be a Jordan cycle is that $S_1$ and $S_2$ should not cross: that is, there should be two arcs of $\gamma$, disjoint except possibly at endpoints, each of which contains one of the $S_i$.

If this condition is satisfied then any planar drawing of $G$ with one component inside and one component outside can be turned into a planar drawing with both components inside by reflecting the outside component in $\gamma$. If the condition is not satisfied then, since the components are connected, there are distinct vertices $x_1$, $x_2$, $y_1$ and $y_2$, appearing in that cyclic order in $\gamma$, such that $x_1$ and $y_1$ are joined by a path in $G_1$, and $x_2$ and $y_2$ are joined by a path in $G_2$. But these paths cannot both be drawn inside $\gamma$.

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$.

Source Link
Ben Barber
  • 4.7k
  • 2
  • 27
  • 39

Let $G_1$ and $G_2$ be adjacent to subsets $S_1$ and $S_2$ respectively of the vertices of $\gamma$. The condition for $\gamma$ to be a Jordan cycle is that $S_1$ and $S_2$ should not cross: that is, there should be two arcs of $\gamma$, disjoint except possibly at endpoints, each of which contains one of the $S_i$.

If this condition is satisfied then any planar drawing of $G$ with one component inside and one component outside can be turned into a planar drawing with both components inside by reflecting the outside component in $\gamma$. If the condition is not satisfied then, since the components are connected, there are distinct vertices $x_1$, $x_2$, $y_1$ and $y_2$, appearing in that cyclic order in $\gamma$, such that $x_1$ and $y_1$ are joined by a path in $G_1$, and $x_2$ and $y_2$ are joined by a path in $G_2$. But these paths cannot both be drawn inside $\gamma$.