Tree reduction during incremental layout

[hasanbalci]

A limited tree reduction can be applied to increase both speed and visual quality of the incremental layout. Generally, incremental layout aims to preserve the mental map of the user, but some cases such as a starlike graph where a node has lots of one-degree neighbors as seen in below image may result in switches on the positions of the one-degree nodes during the incremental layout.

In order to prevent this, if all these one-degree neighbors are in close-to-ideal positions (based on ideal edge length), these nodes together with the root node can be replaced with a single node whose size is as much as the bounding box of the replaced nodes. Towards the end of the layout we can bring the replaced nodes back and apply only a few number of iterations. In this way, the one-degree nodes almost preserve their pre-layout positions according to the root node at the end and we save time from unnecessary repulsion and spring force calculations between these nodes.

This idea can also be considered for the cases where trees with more than one node are connected to the root node instead of one-degree nodes.