leftmost path in planar embedding

Question

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?

Answer 1

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.

Answer 2

A simple planar graph has no notion of left and right, it can be mirrored and rotated still being planar. You have to embed some kind of direction into the graph.

If the maximum out degree of a node is 2 you can label the left edge. To find the left most path you can make a depth first search starting from s. When you reach a new node always take the left edge first. The algorithm should terminate when t is reached, leaving you the the left most path.

In the case of arbitrary maximum out degree you can label the edges with increasing numbers from left to right.