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 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 adjacent vertices (i.e. a walk) which starts with s ...

relations between vertices visually apparent. In dominance drawing, vertices are placed at distinct points of the

Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions ...

and a vertex ''v'' is reachable from another vertex ''u'' if and only if both

Cartesian coordinates A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured i ...

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 segment In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between ...

s, 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 In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

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 Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alo ...

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

, 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 open su ...

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

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

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

, 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 Prentice Hall was an American major educational publisher owned by Savvas Learning Company. Prentice Hall publishes print and digital content for the 6–12 and higher-education market, and distributes its technical titles through the Safari B ...

, 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