Weak Dominance Drawings for Directed Acyclic Graphs

Kornaropoulos, Evgenios M. and Tollis, Ioannis G. (2013) Weak Dominance Drawings for Directed Acyclic Graphs. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 559-560 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_52).

Full text not available from this repository.


The dominance drawing method has many important aesthetic properties, including small number of bends, good vertex placement, and symmetry display [1]. Furthermore, it encapsulates the aspect of characterizing the transitive closure of the digraph by means of a geometric dominance relation among the vertices. A dominance drawing Γ of a planar st-graph G is a drawing, such that for any two vertices u and v there is a directed path from u to v in G if and only if $X(u) ≤ X(v)$ and $Y(u) ≤ Y(v)$ in Γ [1]. Here we study weak dominance drawings where for any two vertices u and v if there is a directed path from u to v in G then $X(u) ≤ X(v)$ and $Y(u) ≤ Y(v)$ in Γ.

Item Type:Conference Poster
Additional Information:10.1007/978-3-642-36763-2_52
Classifications:P Styles > P.720 Straight-line
P Styles > P.999 Others
ID Code:1345

Repository Staff Only: item control page


Di Battista, G., Tamassia, R., Tollis, I.G.: Area Requirement and Symmetry Display of Planar Upward Drawings. Discrete and Comput. Geom. 7(4), 381–401 (1992)

Eades, P., ElGindy, H., Houle, M., Lenhart, B., Miller, M., Rappaport, D., Whitesides, S.: Dominance Drawings of Bipartite Graphs (1993) (manuscript)

Kornaropoulos, E.M., Tollis, I.G.: Weak Dominance Drawings and Linear Extension Diameter, arXiv:1108.1439 (2011)