2
$\begingroup$

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

enter image description here

enter image description here

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

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – MarcoB
    Jan 21, 2022 at 16:14
  • $\begingroup$ 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. $\endgroup$
    – licheng
    Jan 21, 2022 at 16:40

1 Answer 1

0
$\begingroup$

Finding the orientation of the problem requires the algorithm of the following article.

It is equivalent to finding a Schnyder labeling. Sagemath currently has this algorithm built in. This is an alternative.

sage: g = Graph([(0,-1),(0,2),(0,1),(0,-3),(-1,-3),(-1,2),
....: (-1,-2),(1,2),(1,-3),(2,-2),(1,-2),(-2,-3)], format='list_of_edges')
sage: g.set_embedding({-1:[-2,2,0,-3],-2:[-3,1,2,-1],
....: -3:[-1,0,1,-2],0:[-1,2,1,-3],1:[-2,-3,0,2],2:[-1,-2,1,0]})
sage: newg = minimal_schnyder_wood(g)
sage: newg.plot(color_by_label={'red':'red','blue':'blue',
....:  'green':'green',None:'black'})

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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