# Orientations of Planar Graphs

Let $$G$$ be a $$2$$-edge-connected graph drawn in the plane (such that the edges intersect only at the endpoints). I want to orient the edges of $$G$$ such that for each vertex $$v$$, there are no three consecutive edges (in the clockwise direction) such that all of them are oriented towards $$v$$ or all of them are oriented outwards from $$v$$. Does such orientation always exist?

## 1 Answer

Such an orientation always exists, here is a proof.

Take your 2-edge-connected graph $$G$$, and consider its dual graph $$D$$. $$D$$ has a proper 4-coloring in which each face of $$D$$ contains at most 3 different colors (add a vertex inside each face of $$D$$, connect it to all the vertices of the face, and apply the four color theorem to the resulting graph). Now, orient each edge of $$D$$ from the smaller color to the larger color. Note that there is no facial directed path on more that 2 edges in $$D$$ (otherwise, this would be a path with all 4 colors). Now, transfer the orientation of the edges of $$D$$ to the edges of $$G$$ in the natural way, and you get the desired result.

(in the first version of this post, the proof only gave that in 4-edge-connected plane graphs, you can find the desired orientation, and in 2-edge-connected plane graphs, you can find an orientation in which no four consecutive edges around a vertex have the same orientation)

• I slightly modified the proof. Now you have the property that you need. – Louis Esperet Oct 11 '18 at 12:38