MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 added 147 characters in body

## 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?

2 edited body; added 3 characters in body

## 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{grey}{\mathsf{grey}}$) $\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 there are $G - \gamma$ splits up into 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$ 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?

1

# Jordan-like cycles in graphs

## 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{grey}{\mathsf{grey}}$) 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 there are 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$ 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?