Confluent Hasse Diagrams
Eppstein, David and Simons, Joseph A. (2012) Confluent Hasse Diagrams. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 2-13 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_2).
Full text not available from this repository.
We show that a transitively reduced digraph has a confluent upward drawing if and only if its reachability relation has order dimen- sion 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 con- struct 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.
Repository Staff Only: item control page