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?


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.

  • $\begingroup$ @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?) $\endgroup$ – Hans-Peter Stricker Jan 17 '13 at 11:52
  • $\begingroup$ This is a result of Whitney (1933), who also proved that all embeddings of 2-connected graphs can be found as I describe. See math.uwaterloo.ca/~brichter/courses/GT/CO642F11/… for references. Some generalisations to infinite graphs are true too, see ams.org/journals/tran/2002-354-11/S0002-9947-02-03052-0 $\endgroup$ – Brendan McKay Jan 17 '13 at 13:32
  • $\begingroup$ Note that the last sentence wasn't correct and I fixed it, hopefully. $\endgroup$ – 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).

  • $\begingroup$ @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? $\endgroup$ – Hans-Peter 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.

  • $\begingroup$ 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? $\endgroup$ – Rodrigo A. Pérez Jan 17 '13 at 4:10
  • $\begingroup$ Adjacent vertices remain adjacent, don't they? $\endgroup$ – Hans-Peter Stricker Jan 17 '13 at 8:19
  • $\begingroup$ Yes, but the circular order changes. $\endgroup$ – Rodrigo A. Pérez Jan 17 '13 at 18:34
  • $\begingroup$ That's what I meant with "upto orientation". $\endgroup$ – Hans-Peter Stricker Jan 17 '13 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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