| 词条 | Dominance drawing |
| 释义 |
Planar graphsEvery 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][3] 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][3] 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.[7] Nonplanar graphsA 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. CodominanceGiven 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.[9] Weak dominance drawingFor 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.[10] References1. ^1 {{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}}. .[1][2][3][4][5]2. ^1 {{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}}. 3. ^1 2 {{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 | mr = 1148953 | pages = 381–401 | title = Area requirement and symmetry display of planar upward drawings | volume = 7 | year = 1992}}. 4. ^1 2 3 4 {{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}}. 5. ^1 {{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}}. }} 1 : Graph drawing |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。