Dominance drawing

Last updated
A dominance drawing Dominance drawing.svg
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]

Contents

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 D1 = (V, E1), inverting the interpretation of one axis results in a new relation one could call coreachability. Thus a point (xa, ya) could be considered coreachable from a point (xb, yb) whenever xa ≥ xb but ya ≤ yb. In this way, the dominance drawing may be seen to induce a second directed acyclic graph D2 = (V, E2) on the same vertex set. The pairs {≤1, ≤2} 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]

Related Research Articles

Directed acyclic graph Directed graph with no directed cycles

In mathematics, particularly graph theory, and computer science, a directed acyclic graph is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology to sociology to computation (scheduling).

Hypergraph Generalization of graph theory

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Graph drawing 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.

Hasse diagram 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 (S, ≤) one represents each element of S as a vertex in the plane and draws a line segment or curve that goes upward from x to y whenever y covers x . 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.

Feedback arc set 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.

In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex can reach a vertex if there exists a sequence of adjacent vertices which starts with and ends with .

In mathematics, a transitive reduction of a directed graph D is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices v, w a (directed) path from v to w in D exists if and only if such a path exists in the reduction. Transitive reductions were introduced by Aho, Garey & Ullman (1972), who provided tight bounds on the computational complexity of constructing them.

SPQR tree

In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and more specifically graph algorithms, to represent the triconnected components of a graph. The SPQR tree of a graph may be constructed in linear time and has several applications in dynamic graph algorithms and graph drawing.

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity.

In job shop scheduling and graph drawing, the Coffman–Graham algorithm is an algorithm, named after Edward G. Coffman, Jr. and Ronald Graham, 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.

Layered graph drawing Graph drawing with vertices in horizontal layers

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. It is also known as Sugiyama-style graph drawing after Kozo Sugiyama, who first developed this drawing style.

Angular resolution (graph drawing)

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.

In graph theory, a bipolar orientation or st-orientation of an undirected graph is an assignment of a direction to each edge that causes the graph to become a directed acyclic graph with a single source s and a single sink t, and an st-numbering of the graph is a topological ordering of the resulting directed acyclic graph.

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

Anna Lubiw is a computer scientist known for her work in computational geometry and graph theory. She is currently a professor at the University of Waterloo.

In graph drawing, planarization is a method of extending 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.

In graph theory, an st-planar graph is a bipolar orientation of a plane graph for which both the source and the sink of the orientation are on the outer face of the graph. That is, it is a directed graph drawn without crossings in the plane, in such a way that there are no directed cycles in the graph, exactly one graph vertex has no incoming edges, exactly one graph vertex has no outgoing edges, and these two special vertices both lie on the outer face of the graph.

References

  1. 1 2 3 4 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. 1 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" (PDF), Order , 13 (4): 351–364, doi:10.1007/bf00405594, S2CID   121516733 .
  6. ↑ Kornaropoulos, Evgenios M.; Tollis, Ioannis G. (2013), "Weak dominance drawings for directed acyclic graphs", in Didimo, Walter; Patrignani, Maurizio (eds.), Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19-21, 2012, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7704, Springer, pp. 559–560, doi: 10.1007/978-3-642-36763-2_52 .
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.