Unique circular ordering of edges around a vertex - MathOverflow

Unique circular ordering of edges around a vertex

2013-01-16T09:50:48Z

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

Does this property have an official name?

(How) can it be defined purely combinatorially?

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

Answer by Hans Stricker for Unique circular ordering of edges around a vertex

2013-01-16T17:07:12Z

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.

Answer by Michael Biro for Unique circular ordering of edges around a vertex

2013-01-16T19:40:14Z

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

Answer by Brendan McKay for Unique circular ordering of edges around a vertex

2013-01-17T09:45:31Z

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.