# Find the Schnyder 3-orientation of a plane triangulation graph

In 1990, Schnyder proved that the internal edges of a plane triangulation graph can be oriented such that each internal vertex has exactly three outgoing edges and the vertices of the outer face have no outgoing edge.

For a plane triangulation graph, I would like to find the Schnyder 3-orientation.

Schnyder,W.: Embedding planar graphs on the grid. In: Johnson, D.S. (ed.) SODA 1990, pp. 138–148.SIAM (1990)

As can be seen from some literature, software (LEDA) seems to be able to do this. Unfortunately, I'm not familiar with this. I don't know if I can use mathematica to find the above orientation. Looking for such an orientation, the time complexity seems to be O(n) by above same paper.

For a easy example, we obtain the Schnyder 3-orientation of the $$K_4$$. The unique internal vertex "4" has exactly three outgoing edges "41", 42" and "43".

For another example, Schnyder 3-orientation of the plane triangulation graph in the following figure should be obtained by LEDA.

• What have you tried so far? Can you give potential answerers at least something to work on, such as an example graph that you know can be oriented that way? What would you like the output to be? A graphical representation? Jan 21, 2022 at 16:14
• The output does not necessarily have to be a graphical representation , just a set of some directed edges by above 3-oriented . Sorry, I have no idea to start in this question. All I can think of is the possibility of using brute force. Jan 21, 2022 at 16:40

sage: g = Graph([(0,-1),(0,2),(0,1),(0,-3),(-1,-3),(-1,2),