Layered graph drawing

Last updated
A layered drawing of a directed acyclic graph produced by Graphviz DC++ derivatives.svg
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]

Contents

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 sequence of steps:

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]

Related Research Articles

<span class="mw-page-title-main">Graph drawing</span> Visualization of node-link graphs

Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, linguistics, and bioinformatics.

<span class="mw-page-title-main">Hasse diagram</span> Visual depiction of a partially ordered set

In order theory, a Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set one represents each element of as a vertex in the plane and draws a line segment or curve that goes upward from one vertex to another vertex whenever covers . These curves may cross each other but must not touch any vertices other than their endpoints. Such a diagram, with labeled vertices, uniquely determines its partial order.

<span class="mw-page-title-main">Force-directed graph drawing</span> Physical simulation to visualize graphs

Force-directed graph drawing algorithms are a class of algorithms for drawing graphs in an aesthetically-pleasing way. Their purpose is to position the nodes of a graph in two-dimensional or three-dimensional space so that all the edges are of more or less equal length and there are as few crossing edges as possible, by assigning forces among the set of edges and the set of nodes, based on their relative positions, and then using these forces either to simulate the motion of the edges and nodes or to minimize their energy.

<span class="mw-page-title-main">Feedback arc set</span> Edges that hit all cycles in a graph

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing a directed acyclic graph, an acyclic subgraph of the given graph. The feedback arc set with the fewest possible edges is the minimum feedback arc set and its removal leaves the maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

<span class="mw-page-title-main">Book embedding</span> Graph layout on multiple half-planes

In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.

In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

<span class="mw-page-title-main">Graph embedding</span> Embedding a graph in a topological space, often Euclidean

In topological graph theory, an embedding of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs are associated with edges in such a way that:

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

The Coffman–Graham algorithm is an algorithm for arranging the elements of a partially ordered set into a sequence of levels. The algorithm chooses an arrangement such that an element that comes after another in the order is assigned to a lower level, and such that each level has a number of elements that does not exceed a fixed width bound W. When W = 2, it uses the minimum possible number of distinct levels, and in general it uses at most 2 − 2/W times as many levels as necessary.

<span class="mw-page-title-main">Angular resolution (graph drawing)</span> Sharpest angle between edges at a vertex

In graph drawing, the angular resolution of a drawing of a graph is the sharpest angle formed by any two edges that meet at a common vertex of the drawing.

<span class="mw-page-title-main">Peter Eades</span> Australian computer scientist

Peter D. Eades is an Australian computer scientist, an emeritus professor in the School of Information Technologies at the University of Sydney, known for his expertise in graph drawing.

<span class="mw-page-title-main">1-planar graph</span>

In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural generalizations of planar graphs, is drawn that way, the drawing is called a 1-plane graph or 1-planar embedding of the graph.

<span class="mw-page-title-main">Circular layout</span> Graph drawing with vertices on a circle

In graph drawing, a circular layout is a style of drawing that places the vertices of a graph on a circle, often evenly spaced so that they form the vertices of a regular polygon.

<span class="mw-page-title-main">Arc diagram</span> Graph drawing with vertices on a line

An arc diagram is a style of graph drawing, in which the vertices of a graph are placed along a line in the Euclidean plane, with edges being drawn as semicircles in one or both of the two halfplanes bounded by the line, or as smooth curves formed by sequences of semicircles. In some cases, line segments of the line itself are also allowed as edges, as long as they connect only vertices that are consecutive along the line. Variations of this drawing style in which the semicircles are replaced by convex curves of some other type are also commonly called arc diagrams.

<span class="mw-page-title-main">Upward planar drawing</span> Graph with edges non-crossing and upward

In graph drawing, an upward planar drawing of a directed acyclic graph is an embedding of the graph into the Euclidean plane, in which the edges are represented as non-crossing monotonic upwards curves. That is, the curve representing each edge should have the property that every horizontal line intersects it in at most one point, and no two edges may intersect except at a shared endpoint. In this sense, it is the ideal case for layered graph drawing, a style of graph drawing in which edges are monotonic curves that may cross, but in which crossings are to be minimized.

<span class="mw-page-title-main">Dominance drawing</span> Graph where coordinates show reachability

Dominance drawing is a style of graph drawing of directed acyclic graphs that makes the reachability relations between vertices visually apparent. In dominance drawing, vertices are placed at distinct points of the Euclidean plane and a vertex v is reachable from another vertex u if and only if both Cartesian coordinates of v are greater than or equal to the coordinates of u. The edges of a dominance drawing may be drawn either as straight line segments, or, in some cases, as polygonal chains.

<span class="mw-page-title-main">RAC drawing</span>

In graph drawing, a RAC drawing of a graph is a drawing in which the vertices are represented as points, the edges are represented as straight line segments or polylines, at most two edges cross at any point, and when two edges cross they do so at right angles to each other. In the name of this drawing style, "RAC" stands for "right angle crossing".

In the mathematical field of graph theory, planarization is a method of extending graph drawing methods from planar graphs to graphs that are not planar, by embedding the non-planar graphs within a larger planar graph.

In graph drawing, the area used by a drawing is a commonly used way of measuring its quality.

In graph drawing styles that represent the edges of a graph by polylines, it is desirable to minimize the number of bends per edge or the total number of bends in a drawing. Bend minimization is the algorithmic problem of finding a drawing that minimizes these quantities.

References

  1. 1 2 3 4 5 6 7 8 9 10 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. 1 2 3 4 5 6 7 8 9 Bastert, Oliver; Matuszewski, Christian (2001), "Layered drawings of digraphs", in Kaufmann, Michael; Wagner, Dorothea (eds.), Drawing Graphs: Methods and Models, Lecture Notes in Computer Science, vol. 2025, Springer-Verlag, pp. 87–120, doi:10.1007/3-540-44969-8_5, ISBN   978-3-540-42062-0 .
  3. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Healy, Patrick; Nikolov, Nikola S. (2014), "Hierarchical Graph Drawing", in Tamassia, Roberto (ed.), 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, S2CID   8367756 .
  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, ISBN   9780898712513 .
  6. ↑ Eades, P.; Lin, X.; Smyth, W. F. (1993), "A fast and effective heuristic for the feedback arc set problem", Information Processing Letters, 47 (6): 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): 1, doi:10.1145/1411509.1411511, S2CID   1547510 .
  9. 1 2 3 4 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, vol. 2265, Springer-Verlag, pp. 16–30, doi: 10.1007/3-540-45848-4_2 , ISBN   978-3-540-43309-5, 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, S2CID   195722969 .
  12. ↑ Eppstein, David; Goodrich, Michael T.; Meng, Jeremy Yu (2007), "Confluent layered drawings", in Pach, János (ed.), Confluent Layered Drawings, Lecture Notes in Computer Science, vol. 47 (3383 ed.), Springer-Verlag, pp. 184–194, arXiv: cs.CG/0507051 , doi:10.1007/s00453-006-0159-8, S2CID   1169 .
  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. 1 2 Eades, Peter; Wormald, Nicholas C. (1994), "Edge crossings in drawings of bipartite graphs", Algorithmica, 11 (4): 379–403, doi:10.1007/BF01187020, S2CID   22476033 .
  15. ↑ Mäkinen, E. (1990), "Experiments on drawing 2-level hierarchical graphs", International Journal of Computer Mathematics, 36 (3–4): 175–181, doi:10.1080/00207169008803921 .
  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 Computer Science, vol. 2265, Berlin: Springer, pp. 31–44, doi: 10.1007/3-540-45848-4_3 , ISBN   978-3-540-43309-5, 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, vol. 3383, Springer-Verlag, pp. 155–166, doi: 10.1007/978-3-540-31843-9_17 , ISBN   978-3-540-24528-5 .
  19. ↑ Nachmanson, Lev; Robertson, George; Lee, Bongshin (2008), "Drawing Graphs with GLEE" (PDF), in Hong, Seok-Hee; Nishizeki, Takao; Quan, Wu (eds.), Graph Drawing, 15th International Symposium, GD 2007, Sydney, Australia, September 24–26, 2007, Revised Papers, Lecture Notes in Computer Science, vol. 4875, Springer-Verlag, pp. 389–394, doi: 10.1007/978-3-540-77537-9_38 , ISBN   978-3-540-77536-2 .
  20. ↑ Auber, David (2004), "Tulip – A Huge Graph Visualization Framework", in Jünger, Michael; Mutzel, Petra (eds.), 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, vol. 2528, Springer, pp. 366–7, doi: 10.1007/3-540-36151-0_36 , ISBN   978-3-540-00158-4 .
  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, PMID   17356223, S2CID   9852297 .
  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, vol. 45, pp. 69–74, ISBN   9781920682279 .
  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, vol. 6502, Springer, pp. 329–340, doi: 10.1007/978-3-642-18469-7_30 , ISBN   978-3-642-18468-0 .
  25. ↑ Eppstein, David; Goodrich, Michael T.; Meng, Jeremy Yu (2007), "Confluent layered drawings", Algorithmica, 47 (4): 439–452, arXiv: cs/0507051 , doi:10.1007/s00453-006-0159-8, S2CID   1169 .
  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, S2CID   2298634 .
  27. ↑ Cole, Richard (2001). "Automated layout of concept lattices using layered diagrams and additive diagrams". Proceedings of the 24th Australian Computer Science Conference. ACSC 2001. Vol. 23. pp. 47–53. doi:10.1109/ACSC.2001.906622. ISBN   0-7695-0963-0. S2CID   7143873.
  28. ↑ Benno Schwikowski; Peter Uetz & Stanley Fields (2000). "A network of protein−protein interactions in yeast". Nature Biotechnology. 18 (12): 1257–61. doi:10.1038/82360. PMID   11101803. S2CID   3009359.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.