Upward Drawing on the Plane Grid Using Less Ink (Extended Abstract)

Jourdan, Guy-Vincent and Rival, Ivan and Zaguia, Nejib (1995) Upward Drawing on the Plane Grid Using Less Ink (Extended Abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 318-327 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_387).

Full text not available from this repository.

Abstract

Any upward drawing D(P) on a two-dimensional integer grid I, of an ordered set P, has completion \bar{P} with an upward drawing D(\bar{P}) on a two-dimensional integer grid \bar{I} such that the total edge length of D(\bar{P}) does not exceed the total edge length of D(P). Moreover, by (possibly) translating vertices, there is an upward drawing D(P) on I such that \bar{I} = I. Thus, any integer grid embedding of a two-dimensional ordered set can be extended to a planar upward drawing of its completion, on the same integer grid, without increasing the total edge length.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_387
Classifications:P Styles > P.840 Upward
M Methods > M.999 Others
G Algorithms and Complexity > G.070 Area / Edge Length
ID Code:201

Repository Staff Only: item control page

References

A. Aeschlimann and J. Schmid (1992) Drawing orders using less ink, ORDER 9, 5-13.

R. Franzosa, L. Perry, A. Saalfeld, and A. Wohlgemuth (1994) An output-sensitive polynomial-time algorithm for constructing the normal completion of a partially ordered set, preprint.

B. Ganter and K. Reuter (1991) Finding all closed sets : a general approach, ORDER 8, 283-290.

B. Gao, D.-Z. Du, and R. L. Graham, The tight lower bound for the Steiner Ratio in Minkowski planes.

M. R. Garey and D. S. Johnson (1979) Computers and Intractability : A guide to the Theory of NP-Completeness, Freeman, x + 338.

G.-V. Jourdan, J.-X. Rampon, and C. Jard (1994) Computing on-line the lattice of maximal antichains of posets, ORDER (to appear).

J. G. Lee, W.-P. Liu, R. Nowakowski, and I. Rival (1988) Dimension invariance of subdivision, Technical Report TR-88-30, University of Ottawa.

D. Kelly (1977) The 3-irreducible partially ordered sets, Canad. J. Math. 29, 367-383.

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

S. K. Rao, P. Sadayappan, F. K. Hwang, and P. W. Shor (1990) The rectilinear Steiner Arborescence Problem.

E. R. Tufte (1983) The Visual Display of Quantitative Information, Graphics Press, pp. 197.