In the picture below, we have wedge triangles to the left and right of "diagonal edge" e with Schnyder label i + 1. The triangle to the left of e involves the edge e.inc with label i + 2 and the triangle to the right of e involves the edge e.dec with label i. e cannot be swapped with either e.inc or e.dec because all three edges are outgoing from the same vertex v. Either e.inc or e.dec will have to be reversed so that one of them is incoming to vertex v, then a swap with e can be performed.

We can prove that there is always a directed cycle of edges through v that does not include edge e. By reversing this cycle and relabelling edges, we can make either f or g incoming to vertex v.

This cycle will start at either e.inc or e.dec and end at an incoming edge to v between e.inc and e.dec with label i + 1.

If the cycle starts from e.inc with label i + 2, you can traverse the cycle by starting from e.inc then going to the outgoing edge from the vertex pointed to by e.inc (vertex w in the picture below) with label i (edge f in the picture). Next, go to the outgoing edge from vertex x with label i + 1. Keep following outgoing edges with label i + 1 until you get back to vertex v.

If the cycle starts from e.dec with label i, you can traverse the cycle by starting from e.dec then going to the outgoing edge from the vertex pointed to by e.dec (vertex w in the picture below) with label i + 2 (edge f in the picture). Next, go to the outgoing edge from vertex x with label i + 1. Keep following outgoing edges with label i + 1 until you get back to vertex v.

In general, if you let the label of e.inc be i, a directed cycle of edges through v starting from e.inc will have labels as follows:

i --> i + 1 --> i + 2 --> i + 2 --> i + 2 --> i + 2...

If you let the label of e.dec be i, a directed cycle of edges through v starting from e.dec will have labels as follows:

i --> i + 2 --> i + 1 --> i + 1 --> i + 1 --> i + 1...

Since we never know if the directed cycle will start from e.dec or e.inc, we will start from both edges simultaneously and stop when one of the paths take us back to v.

[JSS: would you like to tackle the proof that one of these works?]

To actually construct the cycle, it helps to have a subroutine that, given an edge of label i into a vertex v returns the edge of label i out of vertex v.

edge FollowLabel(edge h)
If triangle to the left of h is mouth
           Let h be h.ccw.ccw.inc
        If triangle to the left of h is cycle
           Let h be h.ccw.ccw.dec
        If triangle to the left of h is wedge
           Let h be h.inc.cw.dec
return h

Here is an algorithm for traversing the directed cycle starting from e.dec. If the directed cycle starts from e.inc, interchange inc and dec, right and left, and cw and ccw. [Considerations: This algorithm doesn't test simultaneously as explained in the paragraph above. Also, I probably need a function that returns the edges of the cycle.] [JSS: yes, you'll want to store the edges visited in arrays, and include the simultaneous exploration. Having a subroutine makes that easier.]

Step 1: Start from e.dec
Step 2: If triangle to the right of e.dec is mouth or cycle
           Let h be e.cw.inc
        Else
           Error! since triangle to the right of e.dec can never be wedge
Step 3: If triangle to the left of h is mouth
           Let h be h.ccw.ccw
        If triangle to the left of h is cycle
           Let h be h.ccw.ccw.inc
        If triangle to the left of h is wedge
           Let h be h.inc.cw.inc
Step 4: while h <> e
           Let h = FollowLabel(h)

-- SisillaSookdeo - 05 Aug 2005

Now for the fun part: reversing the cycle... -- JackSnoeyink - 09 Aug 2005

to top