4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Did you mean to have $G_1$ white . Or more likely to make the 3 gray vertices white and the one white vertex gray? $\endgroup$ Jan 14, 2013 at 14:32
  • $\begingroup$ Is it better understandable now? $\endgroup$ Jan 14, 2013 at 14:36
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 14, 2013 at 16:59
  • $\begingroup$ @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;-) $\endgroup$ Jan 16, 2013 at 17:15

2 Answers 2

2
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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?) $\endgroup$ Jan 14, 2013 at 15:08
  • $\begingroup$ 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$". $\endgroup$
    – Ben Barber
    Jan 14, 2013 at 15:29
  • $\begingroup$ @Ben: thanks for the clarification! $\endgroup$ Jan 14, 2013 at 15:36
  • 1
    $\begingroup$ 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.$ $\endgroup$ Jan 14, 2013 at 17:03
  • $\begingroup$ 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. $\endgroup$
    – Ben Barber
    Jan 14, 2013 at 17:34
2
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ "Falling prey to unchecked details may be regarded as a misfortune; contradicting the given example looks like carelessness." $\endgroup$
    – Ben Barber
    Jan 14, 2013 at 19:16
  • $\begingroup$ @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? $\endgroup$ Jan 21, 2013 at 8:59
  • $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Jan 21, 2013 at 16:35
  • $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Jan 21, 2013 at 17:02
  • $\begingroup$ @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? $\endgroup$ Jan 21, 2013 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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