Algorithm for labeling edges of a triangular mesh
Given any node in the mesh the mesh can be viewed as set of concentric rings around this node (like spider's web). Give all edges that are not in the ring (starred paths) a value of 0, and give all edges that are in the ring (ringed paths) a value of 1. I can't prove it, but I'm certain you will get the correct labeling. Every triangle will have exactly one edge that is part of some ring.
If you order the triangles so that for every triangle at most 2 of its neighbors precede it in the order, then you are set: just color them in this order. The condition guarantees that for each triangle being colored you will always have at least one uncolored edge whose color you can choose so that the condition is satisfied.
Such an order exists and can be constructed the following way:
- Sort all of the vertices left-to-right, breaking ties by top-to-bottom order.
- Sort the triangles by their last vertex in this order.
- When several triangles share the same last vertex, break ties by sorting them clockwise.