MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the property of a vertex $v$ of a planar graph $G$ that the circular ordering of its edges is the same (upto orientation) for every graph embedding $\pi$ of $G$ into the plane $\mathbb{R}^2$.

  1. Does this property have an official name?

  2. (How) can it be defined purely combinatorially?

  3. (How) can planar graphs be characterized in which every vertex has this property?

share|cite|improve this question
up vote 2 down vote accepted

I'm assuming that the reverse of a cyclic ordering counts as the same ordering. I'm also assuming the graph is simple (otherwise subdivide edges with extra vertices to make it simple).

There is only one cyclic order for vertices of degree 1,2,3, so the interesting vertices have degree 4 or more.

3-connected graphs have only one planar embedding. Given any planar embedding of a connected graph, you can get all the other planar embeddings by reordering and flipping over the parts separated by a 1-cut or a 2-cut.

So, without thinking about it too much, I think the answer is:

A vertex has consistent ordering if it has degree 1,2,3, or if it is not a cut-vertex or part of a 2-vertex cut.

A cut-vertex of degree at least 4 does not have consistent ordering.

The remaining case is a vertex $v$ of degree at least 4 that is part of a 2-vertex cut. Separate the graph at the cut so that $v$ and the other vertex in the cut are replicated in each piece (I hope this is clear enough without a formal definition). FIXED: Then $v$ has consistent ordering iff there are exactly two pieces and in one of them $v$ has degree 1.

share|cite|improve this answer
@Brendan: Thanks a lot. Your remark that 3-connected planar (= polyedral) graphs have only one planar embedding did help me a lot. (Is this an elementary or even trivial fact?) – Hans Stricker Jan 17 '13 at 11:52
This is a result of Whitney (1933), who also proved that all embeddings of 2-connected graphs can be found as I describe. See… for references. Some generalisations to infinite graphs are true too, see – Brendan McKay Jan 17 '13 at 13:32
Note that the last sentence wasn't correct and I fixed it, hopefully. – Brendan McKay Jan 18 '13 at 1:54

The converse to the cycle statement doesn't hold. Take a wheel graph, and split each spoke with a new vertex. Then, the center has the fixed circular ordering property, but there is no such cycle.

Intuitively, I suspect the full condition for $v$ to have the property is that there exists in the planar graph a (spoke-divided) wheel graph with $v$ at its center with each of $v$'s neighbors dividing a distinct spoke (where the case of the neighbors being on a cycle is with degenerate spoke-dividing).

share|cite|improve this answer
@Michael: Thanks for the improvement, but it doesn't have to be a proper (spoke-divided) wheel graph: also the "rim" may be divided, doesn't it? – Hans Stricker Jan 17 '13 at 8:23

It might be simpler than I believed:

ad 2. The circular ordering of the edges (= neighbours) of a vertex $v$ of a planar graph $G$ is unique (upto orientation) when the neighbours of $v$ lie on a cycle that does not contain $v$.

If they happen to lie on more than one cycle their circular ordering doesn't depend on which.

share|cite|improve this answer
Take a square and join its vertices to a fifth, central vertex (a 4-wheel). Dragging the center to the outside yields a non-planar embedding, but bending the two offending spokes makes it planar again. Does this not change the circular order around the fifth vertex? – Rodrigo A. Pérez Jan 17 '13 at 4:10
Adjacent vertices remain adjacent, don't they? – Hans Stricker Jan 17 '13 at 8:19
Yes, but the circular order changes. – Rodrigo A. Pérez Jan 17 '13 at 18:34
That's what I meant with "upto orientation". – Hans Stricker Jan 17 '13 at 20:16

Your Answer


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.