Layered graph drawing

A layered drawing of a directed acyclic graph produced by Graphviz

Layered graph drawing or hierarchical graph drawing is a type of graph drawing in which the vertices of a directed graph are drawn in horizontal rows or layers with the edges generally directed downwards.^[1][2][3] It is also known as Sugiyama-style graph drawing after Kozo Sugiyama, who first developed this drawing style.^[4]

The ideal form for a layered drawing would be an upward planar drawing, in which all edges are oriented in a consistent direction and no pairs of edges cross. However, graphs often contain cycles, minimizing the number of inconsistently-oriented edges is NP-hard, and minimizing the number of crossings is also NP-hard, so layered graph drawing systems typically apply a sequence of heuristics that reduce these types of flaws in the drawing without guaranteeing to find a drawing with the minimum number of flaws.

Layout algorithm

The construction of a layered graph drawing proceeds in a sequences of steps:

• If the input graph is not already a directed acyclic graph, a set of edges is identified the reversal of which will make it acyclic. Finding the smallest possible set of edges is the NP-complete feedback arc set problem, so often greedy heuristics are used here in place of exact optimization algorithms.^{[1][2][3][5][6][7]} The exact solution to this problem can be formulated using integer programming.^[3] Alternatively, if the number of reversed edges is very small, these edges can be found by a fixed-parameter-tractable algorithm.^[8]
• The vertices of the directed acyclic graph resulting from the first step are assigned to layers, such that each edge goes from a higher layer to a lower layer. The goals of this stage are to simultaneously produce a small number of layers, few edges that span large numbers of layers, and a balanced assignment of vertices to layers.^[1][2][3] For instance, by Mirsky's theorem, assigning vertices by layers according to the length of the longest path starting from each vertex produces an assignment with the minimum possible number of layers.^[1][3] The Coffman–Graham algorithm may be used to find a layering with a predetermined limit on the number of vertices per layer and approximately minimizing the number of layers subject to that constraint.^[1][2][3] Minimizing the width of the widest layer is NP-hard but may be solved by branch-and-cut or approximated heuristically.^[3] Alternatively, the problem of minimizing the total number of layers spanned by the edges (without any limits on the number of vertices per layer) may be solved using linear programming.^[9] Integer programming procedures, although more time-consuming, may be used to combine edge length minimization with limits on the number of vertices per level.^[10]
• Edges that span multiple layers are replaced by paths of dummy vertices so that, after this step, each edge in the expanded graph connects two vertices on adjacent layers of the drawing.^[1][2]
• As an optional step, a layer of edge concentrator vertices (or confluent junctions) may be imposed between two existing vertex layers, reducing the edge density by replacing complete bipartite subgraphs by stars through these edge concentrators.^[3][11][12]
• The vertices within each layer are permuted in an attempt to reduce the number of crossings among the edges connecting it to the previous layer.^[1][2][3] Finding the minimum number of crossings or finding a maximum crossing-free set of edges is NP-complete, even when ordering a single layer at a time in this way,^[13][14] so again it is typical to resort to heuristics, such as placing each vertex at a position determined by finding the average or median of the positions of its neighbors on the previous level and then swapping adjacent pairs as long as that improves the number of crossings.^{[1][2][9][14][15]} Alternatively, the ordering of the vertices in one layer at a time may be chosen using an algorithm that is fixed-parameter tractable in the number of crossings between it and the previous layer.^[3][16]
• Each vertex is assigned a coordinate within its layer, consistent with the permutation calculated in the previous step.^[1][2] Considerations in this step include placing dummy nodes on a line between their two neighbors to prevent unnecessary bends, and placing each vertex in a centered position with respect to its neighbors.^[3] Sugiyama's original work proposed a quadratic programming formulation of this step; a later method of Brandes and Köpf takes linear time and guarantees at most two bends per edge.^[3][17]
• The edges reversed in the first step of the algorithm are returned to their original orientations, the dummy vertices are removed from the graph and the vertices and edges are drawn. To avoid intersections between vertices and edges, edges that span multiple layers of the drawing may be drawn as polygonal chains or spline curves passing through each of the positions assigned to the dummy vertices along the edge.^[1][2][9]

Implementations

In its simplest form, layered graph drawing algorithms may require O(mn) time in graphs with n vertices and m edges, because of the large number of dummy vertices that may be created. However, for some variants of the algorithm, it is possible to simulate the effect of the dummy vertices without actually constructing them explicitly, leading to a near-linear time implementation.^[18]

The "dot" tool in Graphviz produces layered drawings.^[9] A layered graph drawing algorithm is also included in Microsoft Automatic Graph Layout^[19] and in Tulip.^[20]

Variations

Although typically drawn with vertices in rows and edges proceeding from top to bottom, layered graph drawing algorithms may instead be drawn with vertices in columns and edges proceeding from left to right.^[21] The same algorithmic framework has also been applied to radial layouts in which the graphs are arranged in concentric circles around some starting node^[3][22] and to three-dimensional layered drawings of graphs.^[3][23]

In layered graph drawings with many long edges, edge clutter may be reduced by grouping sets of edges into bundles and routing them together through the same set of dummy vertices.^[24] Similarly, for drawings with many edges crossing between pairs of consecutive layers, the edges in maximal bipartite subgraphs may be grouped into confluent bundles.^[25]

Drawings in which the vertices are arranged in layers may be constructed by algorithms that do not follow Sugiyama's framework. For instance, it is possible to tell whether an undirected graph has a drawing with at most k crossings, using h layers, in an amount of time that is polynomial for any fixed choice of k and h, using the fact that the graphs that have drawings of this type have bounded pathwidth.^[26]

For layered drawings of concept lattices, a hybrid approach combining Sugiyama's framework with additive methods (in which each vertex represents a set and the position of the vertex is a sum of vectors representing elements in the set) may be used. In this hybrid approach, the vertex permutation and coordinate assignment phases of the algorithm are replaced by a single phase in which the horizontal position of each vertex is chosen as a sum of scalars representing the elements for that vertex.^[27] Layered graph drawing methods have also been used to provide an initial placement for force-directed graph drawing algorithms.^[28]

References

1. Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), "Layered Drawings of Digraphs", Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 265–302, ISBN 978-0-13-301615-4.
2. Bastert, Oliver; Matuszewski, Christian (2001), "Layered drawings of digraphs", in Kaufmann, Michael; Wagner, Dorothea, Drawing Graphs: Methods and Models, Lecture Notes in Computer Science 2025, Springer-Verlag, pp. 87–120, doi:10.1007/3-540-44969-8_5.
3. Healy, Patrick; Nikolov, Nikola S. (2014), "Hierarchical Graph Drawing", in Tamassia, Roberto, Handbook of Graph Drawing and Visualization, CRC Press, pp. 409–453 .
4. Sugiyama, Kozo; Tagawa, Shôjirô; Toda, Mitsuhiko (1981), "Methods for visual understanding of hierarchical system structures", IEEE Transactions on Systems, Man, and Cybernetics, SMC-11 (2): 109–125, doi:10.1109/TSMC.1981.4308636, MR 0611436.
5. Berger, B.; Shor, P. (1990), "Approximation algorithms for the maximum acyclic subgraph problem", Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA’90), pp. 236–243.
6. Eades, P.; Lin, X.; Smyth, W. F. (1993), "A fast and effective heuristic for the feedback arc set problem", Information Processing Letters 47: 319–323, doi:10.1016/0020-0190(93)90079-O.
7. Eades, P.; Lin, X. (1995), "A new heuristic for the feedback arc set problem", Australian Journal of Combinatorics 12: 15–26.
8. Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "A fixed-parameter algorithm for the directed feedback vertex set problem", Journal of the ACM 55 (5), doi:10.1145/1411509.1411511.
9. Gansner, E. R.; Koutsofios, E.; North, S. C.; Vo, K.-P. (1993), "A technique for drawing directed graphs", IEEE Transactions on Software Engineering 19 (3): 214–230, doi:10.1109/32.221135.
10. Healy, Patrick; Nikolov, Nikola S. (2002), "How to layer a directed acyclic graph", Graph Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 23–26, 2001, Revised Papers, Lecture Notes in Computer Science 2265, Springer-Verlag, pp. 16–30, doi:10.1007/3-540-45848-4_2, MR 1962416.
11. Newbery, F. J. (1989), "Edge concentration: a method for clustering directed graphs", Proceedings of the 2nd International Workshop on Software Configuration Management (SCM '89), Princeton, New Jersey, USA, Association for Computing Machinery, pp. 76–85, doi:10.1145/72910.73350, ISBN 0-89791-334-5.
12. Eppstein, David; Goodrich, Michael T.; Meng, Jeremy Yu (2004), "Confluent layered drawings", in Pach, János, Proc. 12th Int. Symp. Graph Drawing (GD 2004), Lecture Notes in Computer Science (3383 ed.), Springer-Verlag, pp. 184–194, arXiv:cs.CG/0507051.
13. Eades, Peter; Whitesides, Sue (1994), "Drawing graphs in two layers", Theoretical Computer Science 131 (2): 361–374, doi:10.1016/0304-3975(94)90179-1.
14. Eades, Peter; Wormald, Nicholas C. (1994), "Edge crossings in drawings of bipartite graphs", Algorithmica 11 (4): 379–403, doi:10.1007/BF01187020.
15. Mäkinen, E. (1990), "Experiments on drawing 2-level hierarchical graphs", International Journal of Computer and Mathematics 36: 175–181.
16. Dujmović, Vida; Fernau, Henning; Kaufmann, Michael (2008), "Fixed parameter algorithms for one-sided crossing minimization revisited", Journal of Discrete Algorithms 6 (2): 313–323, doi:10.1016/j.jda.2006.12.008, MR 2418986.
17. Brandes, Ulrik; Köpf, Boris (2002), "Fast and simple horizontal coordinate assignment", Graph drawing (Vienna, 2001), Lecture Notes in Comput. Sci. 2265, Berlin: Springer, pp. 31–44, doi:10.1007/3-540-45848-4_3, MR 1962417.
18. Eiglsperger, Markus; Siebenhaller, Martin; Kaufmann, Michael (2005), "An efficient implementation of Sugiyama’s algorithm for layered graph drawing", Graph Drawing, 12th International Symposium, GD 2004, New York, NY, USA, September 29-October 2, 2004, Revised Selected Papers, Lecture Notes in Computer Science 3383, Springer-Verlag, pp. 155–166, doi:10.1007/978-3-540-31843-9_17.
19. Nachmanson, Lev; Robertson, George; Lee, Bongshin (2008), "Drawing Graphs with GLEE" (PDF), in Hong, Seok-Hee; Nishizeki, Takao; Quan, Wu, Graph Drawing, 15th International Symposium, GD 2007, Sydney, Australia, September 24-26, 2007, Revised Papers, Lecture Notes in Computer Science 4875, Springer-Verlag, pp. 389–394, doi:10.1007/978-3-540-77537-9_38.
20. Auber, David (2004), "Tulip – A Huge Graph Visualization Framework", in Jünger, Michael; Mutzel, Petra, Graph Drawing Software, Springer-Verlag, ISBN 978-3-540-00881-1.
21. Baburin, Danil E. (2002), "Some modifications of Sugiyama approach", Graph Drawing, 10th International Symposium, GD 2002, Irvine, CA, USA, August 26–28, 2002, Revised Papers, Lecture Notes in Computer Science 2528, Springer-Verlag, pp. 366–367, doi:10.1007/3-540-36151-0_36.
22. Bachmaier, Christian (2007), "A radial adaptation of the Sugiyama framework for visualizing hierarchical information", IEEE Transactions on Visualization and Computer Graphics 13 (3): 583–594, doi:10.1109/TVCG.2007.1000.
23. Hong, Seok-Hee; Nikolov, Nikola S. (2005), "Layered drawings of directed graphs in three dimensions", Proceedings of the 2005 Asia-Pacific Symposium on Information Visualisation (APVis '05), Conferences in Research and Practice in Information Technology 45, pp. 69–74.
24. Pupyrev, Sergey; Nachmanson, Lev; Kaufmann, Michael (2011), "Improving layered graph layouts with edge bundling", Graph Drawing, 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers, Lecture Notes in Computer Science 6502, Springer-Verlag, pp. 329–340, doi:10.1007/978-3-642-18469-7_30.
25. Eppstein, David; Goodrich, Michael T.; Meng, Jeremy Yu (2007), "Confluent layered drawings", Algorithmica 47 (4): 439–452, doi:10.1007/s00453-006-0159-8.
26. Dujmović, V.; Fellows, M.R.; Kitching, M.; Liotta, G.; McCartin, C.; Nishimura, N.; Ragde, P.; Rosamond, F.; Whitesides, S. (2008), "On the parameterized complexity of layered graph drawing", Algorithmica 52 (2): 267–292, doi:10.1007/s00453-007-9151-1.
27. Cole, Richard (2001), "Automated layout of concept lattices using layered diagrams and additive diagrams", Proceedings of the 24th Australasian Conference on Computer Science (ACSC '01), pp. 47–53.
28. Benno Schwikowski1, Peter Uetz, and Stanley Fields (2000). "A network of protein−protein interactions in yeast". Nature Biotechnology 18 (12): 1257–1261. doi:10.1038/82360. PMID 11101803.