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 , pp. 2-13(Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_2).

Full text not available from this repository.

Abstract

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.

Item Type:	Conference Paper
Additional Information:	10.1007/978-3-642-25878-7
Classifications:	G Algorithms and Complexity > G.999 Others P Styles > P.300 Curved
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1236

Actions (login required)

View Item