Dominance drawing

A dominance drawing

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.^[1]

Planar graphs

Every transitively reduced st-planar graph, a directed acyclic planar graph with a single source and a single sink, both on the outer face of some embedding of the graph, has a dominance drawing. The left-right algorithm for finding these drawings sets the x coordinate of every vertex to be its position in a depth-first search ordering of the graph, starting with s and prioritizing edges in right-to-left order, and by setting the y coordinate to be obtained in the same way but prioritizing edges in left-to-right order. Typical dominance drawing algorithms include another phase of compaction after this coordinate assignment, shifting vertices down and to the left as much as possible while preserving the properties of a dominance drawing. The resulting drawing lies within an n × n integer grid, and displays many of the symmetries of the underlying topological embedding. This drawing, and more generally every dominance drawing of a transitively-reduced st-planar graph, is necessarily planar, with straight-line edges.^[1][2]

For st-planar graphs that are not transitively reduced, an equivalent transitively reduced graph may be obtained by subdividing each edge. However, a straight-line drawing of the resulting transitively reduced graph will form a drawing of the original graph in which some edges have bends, at the dummy vertices introduced by the subdivision.^[1][2] A planar dominance drawing is not necessarily an upward planar drawing, because some edges may be horizontal, but rotating it by 45° necessarily gives an upward planar drawing.^[1] In a comparison with other methods for drawing directed acyclic graphs, the left-right algorithm (together with a planarization preprocessing step) was found to perform well in terms of the area of the drawings it produces, the number of bends, and the aspect ratio of the drawing, but less well in total edge length.^[3]

Nonplanar graphs

A directed acyclic graph (regardless of planarity) has a dominance drawing if and only if the partially ordered set of its vertices, ordered by reachability, has order dimension two. The (rotated) dominance drawing of a transitively reduced directed acyclic graph may be used as a Hasse diagram of the corresponding partial order.^[4]

Codominance

Given a dominance drawing of a directed acyclic graph D₁ = (V, E₁), inverting the interpretation of one axis results in a new relation one could call coreachability. Thus a point (x_a, y_a) could be considered coreachable from a point (x_b, y_b) whenever x_a ≥ x_b but y_a ≤ y_b. In this way, the dominance drawing may be seen to induce a second directed acyclic graph D₂ = (V, E₂) on the same vertex set. The pairs {≤₁, ≤₂} of partial orders on a shared ground set that permit such simultaneous representation by a single drawing—interpreted in terms of reachability and coreachability—are called codominant.^[5]

Weak dominance drawing

For directed acyclic graphs whose reachability order has higher dimension, a weak dominance drawing is a drawing in which every edge is oriented upwards, rightwards, or both, but in which there exist pairs of vertices (u, v) for which u dominates v coordinatewise but v is not reachable from u in the graph. We said that a vertex u dominates another vertex v if the coordinates (u_x, u_y) of u are less or equal the coordinates (v_x, v_y) of v, i.e., u_x <= v_x and u_y <= v_y considering a XY-plane. The goal in this style of drawing is to minimize the number of such falsely implied paths.^[6]

References

1. Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), "4.7 Dominance Drawings", Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 112–127, ISBN 978-0-13-301615-4.
2. Di Battista, Giuseppe; Tamassia, Roberto; Tollis, Ioannis G. (1992), "Area requirement and symmetry display of planar upward drawings", Discrete and Computational Geometry 7 (4): 381–401, doi:10.1007/BF02187850, MR 1148953.
3. Di Battista, Giuseppe; Garg, Ashim; Liotta, Giuseppe; Parise, Armando; Tamassia, Roberto; Tassinari, Emanuele; Vargiu, Francesco; Vismara, Luca (2000), "Drawing directed acyclic graphs: an experimental study", International Journal of Computational Geometry & Applications 10 (6): 623–648, doi:10.1142/S0218195900000358, MR 1808215.
4. Baker, K. A.; Fishburn, P. C.; Roberts, F. S. (1972), "Partial orders of dimension 2", Networks 2 (1): 11–28, doi:10.1002/net.3230020103.
5. Tanenbaum, Paul J.; Whitesides, Sue (1996), "Simultaneous dominance representation of multiple posets", Order 13 (4): 351–364, doi:10.1007/bf00405594.
6. Kornaropoulos, Evgenios M.; Tollis, Ioannis G. (2013), "Weak dominance drawings for directed acyclic graphs", in Didimo, Walter; Patrignani, Maurizio, Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19-21, 2012, Revised Selected Papers, Lecture Notes in Computer Science 7704, Springer, pp. 559–560, doi:10.1007/978-3-642-36763-2_52.