Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

enter image description here

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?

share|improve this question
    
Did you mean to have $G_1$ white . Or more likely to make the 3 gray vertices white and the one white vertex gray? –  Aaron Meyerowitz Jan 14 '13 at 14:32
    
Is it better understandable now? –  Hans Stricker Jan 14 '13 at 14:36
1  
It is indeed. Guided by the answer below I see that your example with $5$ vertices and $9$ edges shares bragging claims for smallest with another having $6$ vertices and $8$ edges. $K_{3,3}$ minus an edge or equivalently, a $4$-cycle with an additional point connected to each pair of opposite vertices. –  Aaron Meyerowitz Jan 14 '13 at 16:59
    
@Aaron: Sorry for the bragging claim, I should have known better. (In the very last second before submitting the question I changed "seems to me" to "seems to be" - bad mistake!) At least the sum of vertices and edges of your graph is not smaller than that of my graph;-) –  Hans Stricker Jan 16 '13 at 17:15

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
Please give me a clue which question you aim to answer? (Maybe my definition contains a flaw, and you want to give me a hint to that?) –  Hans Stricker Jan 14 '13 at 15:08
    
I intended to answer question 1; sorry for not making that clear. Here's a picture that might help: imagine holding the graph up in $\mathbb{R}^3$; $\gamma$ is Jordan if and only if $G_1$ and $G_2$ can't rotate freely past each other around $\gamma$. The above is just one way of writing that down. I don't have a better answer for 2 than "check the condition for every cycle of $G$". –  Ben Barber Jan 14 '13 at 15:29
    
@Ben: thanks for the clarification! –  Hans Stricker Jan 14 '13 at 15:36
1  
I like the idea, that looks be the answer (provided that being planar is assumed), but you seem to have stated the condition for $\gamma$ to not be a Jordan cycle. So: Let $\gamma$ be a cycle such that $G - \gamma$ has exactly two connected components. Let $S_1,S_2$ be as you say. The condition for $\gamma$ to be a Jordon cycle is that there are 4 vertices $x_1 \ne y_1 \ne x_2 \ne y_2$ (but $x_1=y_2$ is ok) in cyclic order around $\gamma$ so that $x_i \in S_1$ and $y_i \in S_2.$ –  Aaron Meyerowitz Jan 14 '13 at 17:03
    
Yes, I reversed the definition by mistake - I was thinking in terms of "can be drawn with everything inside". I'll edit the answer soon, but first I'd like to double check your final comment: I still think all four vertices need to be distinct to find an obstruction to the "all inside" drawing. –  Ben Barber Jan 14 '13 at 17:34

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.

share|improve this answer
1  
"Falling prey to unchecked details may be regarded as a misfortune; contradicting the given example looks like carelessness." –  Ben Barber Jan 14 '13 at 19:16
    
@Will: I'd like to understand better the connection between 3-connected planar graphs and planar graphs in which every cycle is a Jordan cycle. Does it hold - eventually - that in a 3-connected planar graph every cycle is a Jordan cycle? Or can you give a counter-example? –  Hans Stricker Jan 21 '13 at 8:59
    
No such graphs exist, because every planar graph contains a cycle which does not separate the graph into two components, let alone do so in every embedding. I think the right thing to consider is graphs tha thave only one embedding inthe sphere, up to orientation-preserving homotopy. I think it's clear that these are polyhedral graphs, with the edges subdivided, or otherwise something really trivial like a path. –  Will Sawin Jan 21 '13 at 16:35
    
One might also ask if every graph such that each Jordan curve in one planar embedding is a Jordan curve in another planar embedding has this property. –  Will Sawin Jan 21 '13 at 17:02
    
@Will: Things might look different, if we allow one of the two components to be empty. Does it still hold then, that every planar graphs contains a cycle which does not separate the graph into two components? –  Hans Stricker Jan 21 '13 at 18:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.