Proper interpretation of Sugiyama n-level BC graph layout procedure phase 2

Question

I am trying to understand the Sugiyama graph layout algorithm, as described in the original paper ‘Methods for Visual Understanding of Hierarchical System Structures’.

I understand the basics of the main algorithm: breaking cycles, layering, dummy vertices, reducing crossings, optimizing horizontal positions. I also understand the 2-level BC method (barycentric ordering) for reducing crossings between layers, which iteratively applies phase 1 (stable sort of rows/columns by their barycenter) followed by phase 2 (reversing rows/columns with equal barycenters)

Where I really struggle to interpret the original paper, is in its description of the n-level BC method, which applies a ‘DOWN-UP procedure’ iteratively to first optimize layer crossings by reordering bottom vertices of layers [1..n-1] then reordering top vertices of layers [2..n].

The part I don’t understand is where the ‘phase 2’ (reversal of nodes with equal barycenter) part of the algorithm fits into the n-level method. Contrary to the rest of the paper, this part uses very imprecise & ambiguous wording, and on top of that the example that comes with it does not seem to follow the description.

Specifically, the paper says to solve the crossings iteratively per layer, every iteration containing a DOWN and UP sweep through the layers. It states ‘the above procedure of iteration is called phase 1’. It is not clear to me if ‘phase 1’ means a full DOWN-UP iteration, or an individual DOWN (or UP) sweep. The example in the paper suggests the latter but this is not explicitly stated. The paper then says that ‘when there exists sets of rows (or colums) which have equal barycenters just after execution of phase 1, phase 2 is executed’. The description of phase 2 is as follows:

Phase 2 consists of two procedures, DOWN and UP. In DOWN (or UP) procedure, the order of columns (or rows) in level i with equal barycenters is reversed, and Phase 1 starts with DOWN (or UP) procedure, where i runs 2 through n (or n-1 through 1). When Phase 1 has been terminated with DOWN (or UP) procedure, Phase 2 starts with DOWN (or UP) procedure.

No matter how many times I read this and try to match it to the provided example, I fail to understand what the exact algorithm structure is and how the Phase 1 and 2 are interleaved.

Considering there will be both rows and columns with equal barycenter after reordering, would the main (top-level) iteration be:

1. Phase-1 DOWN, Phase-2 DOWN, Phase-2 UP, Phase-1 UP
2. Phase-1 DOWN, Phase-2 DOWN, Phase-1 UP, Phase-2 UP
3. Phase-1 DOWN, Phase-1 UP, Phase-2 UP, Phase-2 DOWN, Phase-1 DOWN
4. Something else?

The example in the paper on the one hand (the order of the operations performed) suggests it means option 1, but the text that comes with it (‘start of Phase-1 DOWN’ -> ‘end of Phase-1’ -> ‘Phase-2 DOWN’ -> ‘Phase-2 UP’ -> ‘Phase-1 UP’ -> ‘Phase 1 DOWN’ -> ‘end of Phase 2’) confuses me a lot.

I’ve tried to read open-source implementations of the Sugiyama algorithm, but it seems like none of them even bother with the ‘phase 2’ for the n-level BC procedure. Either it’s not that useful, or maybe nobody else fully understands the paper in that regard?

It would be great to have a clear and unambiguous algorithmic specification of the main iteration loop, just the loop structure itself without any details about the individual steps (these are clear).