LR-Upward Drawing of Ordered Sets

• Autorzy: Jourdan G. V. , Rakotomalala V. , Zaguia N.
• Języki publikacji: EN

Abstrakty

EN

In this paper we introduce a new concept to draw an ordered set: the LR- Upward drawing is an upward drawing based on a chain decomposition of the order such that elements drawn on the same vertical line are always comparable and all other comparabilities flow from left to right. We describe a particular technique for automatic generation of an enhanced LR- Upward drawing for N-Free orders that are X-Cycle-Free. This technique first enhances the drawing locally, around a particular chain, and then expands the enhancement to the remaining part of the order. A Java-based implementation is also presented.

Słowa kluczowe

EN

ordered sets; ordered sets visualization; upward drawings; N-Free; X-Cycle-Free

• Wydawca: Institute of Information Technology of the Warsaw University of Life Sciences – SGGW
• Czasopismo: Machine Graphics and Vision
• Rocznik: 2009
• Tom: Vol. 18, No. 1
• Strony: 3--19
• Opis fizyczny: Bibliogr. 14 poz., wykr.

Twórcy

autor

Jourdan G. V.

autor

Rakotomalala V.

autor

Zaguia N.

• School of Information Technology and Engineering (SITE), University of Ottawa, 800 King Edward Avenue, Ottawa, Ontario, Canada, KIN 6N5,

Bibliografia

• [1] E. Szpilrajn. Sur l'extension de Fordre partiel. Fund. Math., (16): 86-389, 1930.
• [2] R. P. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics,(51): 161-166, 1950.
• [3] J. Hopcroft, R. E. Tarjan. Efficient planarity testing. J. ACM, 21(4):549-568, 1974.
• [4] I. Rival. Optimal linear extensions by interchanging chains. Proc. American Math. Society,(89): 387-394, 1983.
• [5] I. Rival. The diagram. In I. Rival, editor, Graphs and Orders, pages 103-133. Reidel Publishing, 1985.
• [6] I. Rival. Stories about order and the letter n (en). Contemporary Mathematics, (57), 1986.
• [7] I. Rival, N. Zaguia. Constructing greedy linear extensions by interchanging chains. Order, (3): 107-121, 1986.
• [8] I. Rival. Reading, drawing, and order. In I. G. Rosenberg and G. Sabidussi, editors, Algebras and Orders, pages 359-404. Kluwer Academic Publishers, 1993.
• [9] G. Di Battista, P. Eades, R. Tamassia, I. G. Tollis. Algorithms for drawing graphs: an annotated bibliography. Comput. Geom. Theory Appl, 4: 235-282, 1994.
• [10] C. Lin. The crossing number of posets. Order, 11: 169-193, 1994.
• [11] A. Garg, R. Tamassia. Upward planarity testing. Order, 12: 109-133, 1995.
• [12] G. Di Battista, P. Eades, R. Tamassia, I. G. Tollis. In Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.
• [13] algorithmic solutions. Graphwin. http://www.algorithmic-solutions.info/leda_guide/graphwin.html, 2003.
• [14] R. Freese. Lattices drawing software: Latdraw. http://www.math.hawaii.edu/ralph/LatDraw, 2005.