Two-dimensional packing algorithms for layout of disconnected graphs

Dogrusoz, Ugur (2002) Two-dimensional packing algorithms for layout of disconnected graphs. [Journal (On-line/Unpaginated)]

Full text not available from this repository.

Abstract

We present and contrast several efficient two-dimensional packing algorithms for specified aspect ratio. These near-linear algorithms are based on strip packing, tiling, and alternate-bisection methodologies and can be used in the layout of disconnected objects in graph visualization. The parameters that affect the performance of these algorithms as well as the circumstances under which they perform well are analyzed.

Item Type:Journal (On-line/Unpaginated)
Additional Information:10.1016/S0020-0255(02)00183-4
Keywords:two-dimensional packing
Classifications:G Algorithms and Complexity > G.560 Geometry
Z Theory > Z.250 Geometry
ID Code:738

Repository Staff Only: item control page

References

G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Algorithms for drawing graphs: an annotated bibliography. In: Comput. Geom. Theory Appl., 4 (1994), pp. 235–282.

E.G. Coffman, M.R. Garey, D.S. Johnson, R.E. Tarjan: Performance bounds for level-oriented two-dimensional packing algorithms. In: SIAM J. Comput., 9 (4) (1990), pp. 808–826.

B.S. Baker, E.G. Coffman, R.S. Rivest Orthogonal packings in two dimensions. In: SIAM J. Comput., 9 (4) (1980), pp. 846–855.

E.G. Coffman, P.W. Shor: Packings in two dimensions: asymptotic average case analysis of algorithms. In: Algorithmica, 9 (1993), pp. 253–277.

E.G. Coffman, M.R. Garey, D.S. Johnson: Approximation algorithms for bin packing: an updated survey. In: G. Ausiello, M. Lucertini, P. Serafini (Eds.): Algorithm Design for Computer System Design, Springer, New York (1984), pp. 49–106.

R. Korf: From approximate to optimal solutions: a case study of number partitioning. In: Proceedings of the 14th IJCAI, Montreal, Canada (1995), pp. 266–272.

G.S.L.N.K. Karmarker, R.M. Karp, A.M. Odlyzko: Probabilistic analysis of optimum partitioning. In: J. Appl. Probab., 23 (1986), pp. 626–645.

T. Lengauer: Combinatorial Algorithms for Integrated Circuit Layout. Wiley, New York (1990).