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.

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
ID Code:1236

Repository Staff Only: item control page

References

Aeschlimann, A., Schmid, J.: Drawing orders using less ink. Order 9(1), 5–13 (1992)

Amer, P., Chassot, C., Connolly, T., Diaz, M., Conrad, P.: Partial-order transport service for multimedia and other applications. IEEE/ACM Transactions on Networking 2(5), 440–456 (1994)

Baker, K.A., Fishburn, P.C., Roberts, F.S.: Partial orders of dimension 2. Networks 2(1), 11–28 (1972)

Bertolazzi, P., Di Battista, G., Mannino, C., Tamassia, R.: Optimal upward planarity testing of single-source digraphs. SIAM J. Comput. 27(1), 132–169 (1998)

Birkhoff, G.: Lattice Theory. American Mathematical Society, Providence (1967)

Di Battista, G., Tamassia, R.: Algorithms for plane representations of acyclic digraphs. Theoret. Comput. Sci. 61(2-3), 175–198 (1988)

Dickerson, M.T., Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent drawings: visualizing non-planar diagrams in a planar way. J. Graph Algorithms Appl. 9(1), 3–52 (2005),http://jgaa.info/accepted/2005/Dickerson+2005.9.1.pdf

Eppstein, D., Goodrich, M.T., Meng, J.Y.: Delta-Confluent Drawings. In: Healy, P.,Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 165–176. Springer, Heidelberg (2006)

Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent layered drawings. Algorithmica 47(4), 439–452 (2007)

Gansner, E., Hu, Y., North, S., Scheidegger, C.: Multilevel agglomerative edge bundling for visualizing large graphs. In: IEEE Pacific Visualization Symposium (PacificVis), pp. 187–194 (2011)

Ganter, B., Kuznetsov, S.O.: Stepwise Construction of the Dedekind-MacNeille Completion. In: Mugnier, M.-L., Chein, M. (eds.) ICCS 1998. LNCS (LNAI), vol. 1453, pp. 295–302. Springer, Heidelberg (1998)

Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601–625 (2002)

Gü̈ting, R.H., Nurmi, O., Ottmann, T.: Fast algorithms for direct enclosures and direct dominances. J. Algorithms 10(2), 170–186 (1989)

de la Higuera, C., Nourine, L.: Drawing and encoding two-dimensional posets.Theoret. Comput. Sci. 175(2), 293–308 (1997)

Hirsch, M., Meijer, H., Rappaport, D.: Biclique Edge Cover Graphs and Confluent Drawings. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp.405–416. Springer, Heidelberg (2007)

Hui, P., Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Train tracks and confluent drawings. Algorithmica 47(4), 465–479 (2007)

Hutton, M.D., Lubiw, A.: Upward planar drawing of single source acyclic digraphs.SIAM J. Comput. 25(2), 291–311 (1996)

Jourdan, G.V., Rival, I., Zaguia, N.: Upward Drawing on the Plane Grid Using Less Ink. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 318–327.Springer, Heidelberg (1995)

Kelly, D., Rival, I.: Planar lattices. Canad. J. Math. 27(3), 636–665 (1975)

Lodaya, K., Weil, P.: Series-Parallel Posets: Algebra, Automata and Languages.In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 555–565.Springer, Heidelberg (1998)

Ma, T.H., Spinrad, J.: Transitive closure for restricted classes of partial orders.Order 8(2), 175–183 (1991)

MacNeille, H.M.: Partially ordered sets. Trans. Amer. Math. Soc. 42(3), 416–460 (1937)

Mannila, H., Meek, C.: Global partial orders from sequential data. In: Proceedings of the sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2000, pp. 161–168. ACM, New York (2000)

Mö̈hring, R.H.: Computationally tractable classes of ordered sets. In: Rival, I. (ed.) Algorithms and Order, pp. 105–193. Kluwer Academic Publishers (1989)

Mö̈hring, R.H., Schä̈ffter, M.W.: Scheduling series-parallel orders subject to 0/1-communication delays. Parallel Comput. 25(1), 23–40 (1999)

Nourine, L., Raynaud, O.: A fast algorithm for building lattices. Inform. Process.Lett. 71(5-6), 199–204 (1999)

Novák V.: Über eine Eigenschaft der Dedekind-MacNeilleschen Hülle. Math.Ann. 179, 337–342 (1969)

Platt, C.R.: Planar lattices and planar graphs. J. Combinatorial Theory, Ser. B 21(1), 30–39 (1976)