Dominance drawing is a style of

graph drawing 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, car ...

directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one v ...

s that makes the

reachability In graph theory, reachability refers to the ability to get from one Vertex (graph theory), vertex to another within a graph. A vertex s can reach a vertex t (and t is reachable from s) if there exists a sequence of Glossary of graph theory#Basics, ...

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 chain In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain is a curve specified by a sequence of points (A_1, A_2, \dots, A_n) called its vertices. The curve itself consists of the line segments co ...

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. 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. A planar dominance drawing is not necessarily an

upward planar drawing 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 ...

, because some edges may be horizontal, but rotating it by 45° necessarily gives an upward planar drawing. 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 Area is the quantity that expresses the extent of a region on the plane or on a curved surface. The area of a plane region or ''plane area'' refers to the area of a shape or planar lamina, while '' surface area'' refers to the area of an ope ...

of the drawings it produces, the number of bends, and the aspect ratio of the drawing, but less well in total edge length.

Nonplanar graphs

A directed acyclic graph (regardless of planarity) has a dominance drawing if and only if the

partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a bina ...

of its vertices, ordered by reachability, has

order dimension In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order. This concept is also sometimes called the order dimension or the Dushnik–Miller di ...

two. The (rotated) dominance drawing of a transitively reduced directed acyclic graph may be used as a

Hasse diagram 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 ''(S, ≤)'' one represents ...

of the corresponding partial order.

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.''

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''.

References

{{reflist, 3oem, refs= {{citation , last1 = Baker , first1 = K. A. , last2 = Fishburn , first2 = P. C. , author2-link = Peter C. Fishburn , last3 = Roberts , first3 = F. S. , author3-link = Fred S. Roberts , doi = 10.1002/net.3230020103 , issue = 1 , journal = Networks , pages = 11–28 , title = Partial orders of dimension 2 , volume = 2 , year = 1972. {{citation , last1 = Di Battista , first1 = Giuseppe , last2 = Garg , first2 = Ashim , last3 = Liotta , first3 = Giuseppe , last4 = Parise , first4 = Armando , last5 = Tamassia , first5 = Roberto , author5-link = Roberto Tamassia , last6 = Tassinari , first6 = Emanuele , last7 = Vargiu , first7 = Francesco , last8 = Vismara , first8 = Luca , doi = 10.1142/S0218195900000358 , issue = 6 , journal = International Journal of Computational Geometry & Applications , mr = 1808215 , pages = 623–648 , title = Drawing directed acyclic graphs: an experimental study , volume = 10 , year = 2000. {{citation , last1 = Tanenbaum , first1 = Paul J. , last2 = Whitesides , first2 = Sue , pages = 351–364 , title = Simultaneous dominance representation of multiple posets , journal = Order , volume = 13 , issue = 4 , year = 1996 , doi=10.1007/bf00405594, s2cid = 121516733 , url = https://hal.inria.fr/inria-00074062/file/RR-2624.pdf . {{citation , last1 = Di Battista , first1 = Giuseppe , last2 = Tamassia , first2 = Roberto , author2-link = Roberto Tamassia , last3 = Tollis , first3 = Ioannis G. , doi = 10.1007/BF02187850 , issue = 4 , journal =

Discrete and Computational Geometry '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational geome ...

, mr = 1148953 , pages = 381–401 , title = Area requirement and symmetry display of planar upward drawings , volume = 7 , year = 1992, doi-access = free . {{citation , last1 = Di Battista , first1 = Giuseppe , last2 = Eades , first2 = Peter , author2-link = Peter Eades , last3 = Tamassia , first3 = Roberto , author3-link = Roberto Tamassia , last4 = Tollis , first4 = Ioannis G. , contribution = 4.7 Dominance Drawings , isbn = 978-0-13-301615-4 , pages = 112–127 , publisher = Prentice Hall , title = Graph Drawing: Algorithms for the Visualization of Graphs , year = 1998. {{citation , last1 = Kornaropoulos , first1 = Evgenios M. , last2 = Tollis , first2 = Ioannis G. , editor1-last = Didimo , editor1-first = Walter , editor2-last = Patrignani , editor2-first = Maurizio , contribution = Weak dominance drawings for directed acyclic graphs , doi = 10.1007/978-3-642-36763-2_52 , pages = 559–560 , publisher = Springer , series = Lecture Notes in Computer Science , title = Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19-21, 2012, Revised Selected Papers , volume = 7704 , year = 2013, doi-access = free . Graph drawing