Wrapping layered graphs

We present additions to the widely-used layout method for directed acyclic graphs of Sugiyama et al. [16] that allow to better utilize a prescribed drawing area. The method itself partitions the graph's nodes into layers. When drawing from top to bottom, the number of layers directly impacts the height of a resulting drawing and is bound from below by the graph's longest path. As a consequence, the drawings of certain graphs are significantly taller than wide, making it hard to properly display them on a medium such as a computer screen without scaling the graph's elements down to illegibility. We address this with the Wrapping Layered Graphs Problem (WLGP), which seeks for cut indices that split a given layering into chunks that are drawn side-by-side with a preferably small number of edges wrapping backwards. Our experience and a quantitative evaluation indicate that the proposed wrapping allows an improved presentation of narrow graphs, which occur frequently in practice and of which the internal compiler representation SCG is one example.


Logo BII



Use and reproduction:

No license. The provisions of the German Copyright Act (UrhG) apply.

Please note that individual components of the publication may be subject to other licensing or copyright conditions.


Citation style:
Could not load citation form.