I have a directed planar Graph. Therefore I can make a planar embedding. I have to nodes s and t and I would like to find the leftmost path between s and t according to a specific embedding.
Left is defined as David described in the comment. That means "Left" is defined with respect to an infinite face and a clockwise/counterclockwise convention. A path p is left of a path q with the same endpoints if the cycle p*rev(q) is at least as counterclockwise with respect to winding the infinite face as any other face.
How is that possible? I have no idea how to tell my programm if a path is left of another one. I read a few paper, but they didn't explain how to implement that. Does someone has an idea?
As user3568609 notes, the planar embedding is on a sphere, with no natural definition of left and right. You need to choose an infinite face first; for flow algorithms (I assume that this is what you’re implementing), it’s often convenient to choose a face incident to s or t. Let’s suppose that the infinite face is incident to t. The counterclockwise order of half-edges into t now has a natural gap where the infinite face is.
.4 3| /2 .
\___|/___/
t 1
(infinite face)
Visit the half-edges in counterclockwise order, 1 to 4 in the example. This is a depth-first traversal, so we fully explore 1’s connections before 2’s, etc. When you arrive at another vertex v from another vertex u then the picture looks like this
|3 |2
\___|___/1
v
|
u
Once again I’ve labeled the proper traversal order.