Let $G$ be an undirected planar graph. Any specific planar embedding of $G$ induces a "clockwise neighbor" function $r$ which sends each dart $u-v$ to the dart $u-v^\prime$, where $v^\prime$ is the immediately-clockwise neighbor of $v$ around $u$. (Note: a "dart" is an edge where one of the endpoints is marked special, so each edge gives rise to exactly two possible darts.)
Suppose an arbitrary permutation of darts $p$ behaves sort of like a clockwise neighbor function, i.e.
- $p$ fixes the special endpoint of each dart: each dart $u-v$ is sent to a dart of the form $u-v^\prime$,
- $p$ doesn't have any weird cycles: if $u$ is a vertex of degree $k$, then $p^k$ maps every dart of the form $u-v$ onto itself. But $p^\ell$ does not map any dart $u-v$ onto itself if $1\leq \ell < k$.
Are these conditions sufficient to guarantee that a planar embedding exists whose clockwise neighbor function is $p$? If not, what further conditions are necessary?
I think the conditions are not strong enough by themselves, because they describe merely local constraints around each vertex without enforcing global compatibility. For example, the stated properties do not make it clear why, in a non-planar graph, every permutation of darts fails to correspond to a clockwise-neighbor function $R$.
For a concrete example, consider the following graph with five vertices:
The picture on the left corresponds to a clockwise-neighbor function $p_1$ which sends $ab \leftarrow ac \leftarrow ad \leftarrow ab$ and sends $da \leftarrow dc \leftarrow de \leftarrow da$.
Similarly, the picture on the right corresponds to a different clockwise neighbor function $p_2$ which sends $ab \leftarrow ad \leftarrow ac \leftarrow ab$ and sends $da \leftarrow de \leftarrow dc \leftarrow da$.
But I think there is no embedding corresponding to the permutation $p_3$ which combines these, sending $ab \leftarrow ac \leftarrow ad \leftarrow ab$ and $da \leftarrow de \leftarrow dc \leftarrow da$ because these two local permutations are incompatible with each other. If you tried to satisfy them both, you'd get an edge crossing in the resulting embedding.
I think it might be possible to express the conditions that govern whether a local derangement of darts around one vertex is compatible with a local derangement of darts around another vertex. I have considered searching for an algebraic expression,For example, it might be possible to find an assignment of values onto the vertices/edges/faces of $G$ such that if $p$ respects the value assignment, then $p$ is a valid rotation. Or possibly an expression in terms of the cycle space. I am not sure how to proceed from here, though.
Edit: I found an elegant characterization of darts: If $\mathbf{2}$ is the undirected graph consisting of two vertices and an edge between them, then the darts of $G$ correspond to the graph homomorphisms $\mathbf{2}\rightarrow G$.
Best Answer
So far you have described general combinatorial maps, but for planarity you need just one additional condition that is relatively easy to calculate. Let $d$ be the permutation on darts that sends each dart $u-v$ to the opposite dart $v-u$. A face is a subset of darts that is an orbit of the permutation $p\circ d$. When you have embedded a graph in the plane, then faces in this sense correspond to faces in the usual sense.
Let $v$ be the number of vertices, $e$ the number of edges (so half the number of darts), and $f$ the number of faces. This is the additional condition:
This is the genus condition. In general, if the graph is connected and $g$ is a number satisfying $v-e+f=2-2g$, then $g$ is the smallest non-negative integer such that the graph can be embedded in a genus-$g$ surface. The quantity $v-e+f$ is known as the Euler characteristic.
To summarize, conditions 1-3 are necessary and sufficient for $p$ to correspond to a planar embedding.