Journal of Graph Algorithms and Applications
|Home||Issues||Aims and Scope||Instructions for Authors|
Confluent Hasse Diagrams
Vol. 17, no. 7, pp. 689-710, 2013. Regular paper.
Abstract We show that a transitively reduced digraph has a confluent upward drawing if and only if its reachability relation has order dimension at most two. In this case, we construct a confluent upward drawing with O(n2) features, in an O(n) ×O(n) grid in O(n2) time. For the digraphs representing series-parallel partial orders we show how to construct a drawing with O(n) features in an O(n) ×O(n) grid in O(n) time from a series-parallel decomposition of the partial order. Our drawings are optimal in the number of confluent junctions they use.
Submitted: April 2013.
Reviewed: July 2013.
Revised: November 2013.
Accepted: November 2013.
Final: November 2013.
Published: November 2013.
Communicated by Antonios Symvonis