StretchWidth

StretchWidth is a layering algorithm proposed by Nikolas S. Nikolov, Alexandre Tarassov, and Jürgen Branke

in "In Search for Efficient Heuristics for Minimum-Width Graph Layering with Consideration of Dummy Nodes"

The description of this algorithm in this page refers to a top-down graph and so it may differ from the description of other algorithm in KLay Layered. The algorithm tries to minimize the width of the layered graph by trying to apply a boundary in every layer and increasing this boundary, if it fails (e.g. if it would create an empty layer).

This approach first orders the nodes by their rank. Whereby the rank of a node v is defined as the maximum of the incoming edges in v and the maximum of the outgoing edges of all predecessors. Then it starts by the bottom of the graph and places the layerless node with the highest rank, whose successors are all already placed in a layer below. While placing the width of the actual layer and an estimation of the width of the next layer was taken into account. If the placement of a node would violate the boundary, the algorithm starts with the next layer.

Precondition: the graph has no cycles, but might contain self-loops.

Postcondition: all nodes have been assigned a layer such that edges  connect only nodes from layers with increasing indices.

Implementation

In the first approach the checking if the algorithm should start a new layer was missinterpreted as " we first place the node and than we check if the boundary is violated". This includes that a placed node would only return to the layerless state if the algorithm restarts with the increased boundary.

Since this condition go up (CGU) would mostly result in a longest-path-layering, a variable was added to control the influence of the estimated next layer. It ranged from 0.0 to 1.0. Where 0.0 would result in a layering very similar to an one-node-layerer and 1.0. would again be the longest-path-layerer. In between were multiple nuances, whose nodes per layer  increased monotonically from 0.0 to 1.0.

The actual CGU only hypothetically places the node and only if it doesn't violate the boundary, the node will be placed. With this CGU we were able to reproduce the results from the Paper in which the algorithm was proposed, but naturally the added variable doesn't work as clear as before.

The evaluation of this variable indicates that downscaling of this upper layer bound results in smaller drawings. But it has yet to be evaluated for the pencil-metric.

Both following pictures show the width of the graphs. Orthogonal edge routing, the BK-node-placer and node promotion were used. In this case the used pixel were measured. The first image contains the results of StretchWidth with the original factor, the average out-degree. In this case StretchWdith ist similar to LongestPath and a little to Networksimplex. The second diagram shows the results of other, fixed scaling factors between 0.1 and 1.0. The width is reduced (and the height increased) indicating that there is an better value, improving the original algorithm.

Real Node Sizes

The original algorithm does not consider real node sizes. Every node and every dummy node has the same size and do not need to be differed.

The authors stated, that an implementation with real sizes should be easy. But we think that an simple addition of the real size or a normalized size (maybe by the smallest node)  would reduce the validity of the rank and the upper layer estimation.

This task is still open.

Node Promotion

Since StretchWidth, like MinWidth, creates many dummy-nodes in the layering, the authors recommend to use the node promotion as a post-processing step.

Our measurements show indeed, that the results improve. However the measurements show also, that node promotion doesn't have the huge impact as by Minwidth. The first Diagram shows the number of dummy nodes normalized by the number of original nodes. The results in second diagram have one through the additional post-processing of node promotion. The tendency may look the same, but it is important to notice the change in the y-scale.

First Results

We were able to recreate the results from the proposing paper.  As additional characteristics we also measured the width and height in pixel and the pencil-metric.

We used orthogonal edge-routing and the BK-node-placer. As expected the results are very similar to longest-path, especially with increasing node count.

One example is the pencil-metric for one Din A4 sheet: the first without node promotion and at the second with this post-processing step.

Both diagrams are normalized by the pencil-metric of Network Simplex to get an qualitative comparison.

Future Work ?