Outdegree, contractions, planar graphs

You can always direct the edges of a planar graph so that every vertex has outdegree at most 5. That fact is clear to anyone who has taken a discrete math course at one point in their life.

My question is:
Q: What happens if the edges of the graph get contracted one by one?
A: Then the outdegree risks growing. For example, if one contracts two adjacent vertices that each have outdegree 5, the resulting vertex will then have outdegree 5+5-1=9. The next contraction may bring its degree up to 9+5-1=13, then 17, etc.

My question then is:
Q: Is it possible to efficiently modify the orientation of some edges along the way and prevent the outdegree from blowing up?
A: Yup. Here's the algorithm, appealingly simple and natural. After each contraction, do the following: while there exists a vertex v of outdegree greater than 10, reverse the orientation of every outgoing edge of v.

At this point your question surely is or should be:
Q (Toto): Cute, maybe, if that's your taste, but why do you care?
A: Because it is used in an upcoming SODA paper by David Eisenstat, Philip Klein and myself, to reduce the runtime of a primal-dual region-growing phase.

Now that the motivation is out of the way, we can think about it together.
Q (Toto): Ok, I'm willing to temporarily accept that this might be interesting. Then, why does this algorithm work and how efficient is it?
A: By design, it obviously maintains an orientation in which each vertex has outdegree no more than 10. The neat observation is that it is an efficient algorithm: the total number of reversals, and hence the runtime (assuming you don't mess up the low-level implementation details), is O(n log n).

Q (Toto): Why is the total number of reversals O(n log n)? I don't see it.
A: The proof is magic.
Q (Toto): I don't like magic.
A: The magic would disappear if you did a few examples of amortized analysis, but for a single analysis of a single problem, you have to accept the magic. Let G(i) be the graph after i contractions. We consider two orientations of the edges of G(i): Alg(G(i)), the orientation obtained by executing the algorithm, and a certain orientation Ideal(G(i)) such that the maximum outdegree in Ideal(G(i)) is at most 5. To start the proof, magically define the potential of G(i) to be
Potential(G(i))= distance(Alg(G(i),Ideal(G(i))), that is, the number of edges that are oriented differently in the two orientations.

Now, here's my question.
Q: What happens to the potential when the algorithm reverses all the outgoing edges of a vertex v?
A: That's not hard to see. Let S denote that group of edges. Immediately before the reversal of S, in Alg the outdegree of v is |S|>=11, and in Ideal the outdegree is <=5, so S contributes at least |S|-5 to the distance; immediately after the reversal of S, S contributes at most 5 to the distance. So the reversal of S has caused the distance to decrease by at least (|S|-5-5)>=1. Overall the total number of edge reversals is within a constant factor of (sum of decreases in the potential function): instead of analyzing the number of edge reversals, we can just analyze the number of decreases of the potential function.

Q (Toto): Big deal. It's not clear to me that you have made any progress: how do you analyze the number of decreases of the potential function?
A: Let's see. Since the potential function is always non-negative, each decrease must be compensated by some previous increase (or by the initial value). So, the total number of decreases is at most the initial value of the potential (which is O(n)), plus the increases that may happen when going from Ideal(G(i)) to Ideal(G(i+1)).

Q (Toto): But you haven't even told me what that "certain orientation Ideal(G(i))" was! I am frustrated.
A: Patience! It is now time to define Ideal(G(i)). Let's do it in backwards order.
Q (Toto): Why? I am frustrated.
A: Because that's what works. Be quiet! Start from the final graph, give it an orientation such that the maximum outdegree is 5, and "uncontract" the edges one by one. To define Ideal(G(i)) from Ideal(G(i+1)), do the following. After the uncontraction of edge uv, in the orientation of G(i) that is inherited from G(i+1), vertex u and vertex v each have outdegree at most 5, and edge uv needs to be given an orientation: arbitrarily direct it from u to v; if u now has degree 6, find a shortest path p (in the directed graph) from u to a vertex with outdegree less than or equal to 4, and reverse the orientation of every edge on p. Now the outdegree of u is reduced to 5. That defines Ideal(G(i)).

Q (Toto): I'm tired. Are we there yet?
A: To finish the proof, it only remains to observe that p has length O(log n).

Q (Toto): Why does p have length O(log n)? Oh, whatever.
A: Easy. Do breadth first search from u. How can it be that all vertices in the first i levels have degree >=5? From Euler's formula for planar graphs, it is easy to see (it's an exercise) that it can only happen if the growth rate is exponential, and such a growth rate can only be maintained for O(log n) levels.

Q (Toto): If you say so. Whatever.
A: Hang on! We're done, just about: So p has length O(log n), so Ideal(G(i)) differs from Ideal(G(i+1)) in O(log n) edges, so the potential can only increase by O(log n) at each contraction, so it can only increase by O(n log n) overall, so it can only decrease by O(initial value + n log n), so the total number of edges reversals is O(n + n log n)=O(n log n) overall, so the algorithm is efficient. I'm done.

My last question:
Q: Isn't it elegant, simple, and clever?
A (Toto): I guess so. You certainly seem excited about it.

Your final question is:
Q (Toto): How do you know all that stuff?
A: The basic technique is from Brodal and Fagerberg, "Dynamic Representations of Sparse Graphs." The application to contractions is from Kowalik, "Fast 3-coloring triangle-free planar graphs". It's also explained in an upcoming textbook by Philip Klein.