Home | Issues | About JGAA | Instructions for Authors |
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
|
Journal Supporters
|