A Layout Adjustment Problem for Disjoint Rectangles Preserving Orthogonal Order

Hayashi, Kunihiko and Inoue, Michiko and Masuzawa, Toshimitsu and Fujiwara, Hideo (1998) A Layout Adjustment Problem for Disjoint Rectangles Preserving Orthogonal Order. In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 183-197 (Official URL: http://dx.doi.org/10.1007/3-540-37623-2_14).

Full text not available from this repository.

Abstract

For a given set of n rectangles place on a plane, we consider a problem of finding the minimum area layout of the rectangles that avoids intersections of the rectangles and preserves the orthogonal order. Misue et al. proposed an O(n²)-time heuristic algorithm for the problem. We first show that the corresponding decision problem for this problem is NP-complete. We also present an O(n²)-time heuristic algorithm for the problem that finds a layout with smaller area than Misue's.

Item Type:Conference Paper
Additional Information:10.1007/3-540-37623-2_14
Classifications:G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.070 Area / Edge Length
ID Code:245

Repository Staff Only: item control page

References

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. Theory Appl., 4:235-282, 1994.

R. Tamassia, G. Di Battista, and C. Batini. Automatic graph drawing and readability of diagrams. IEEE Transactions on Systems, Man and Cybernetics, SMC-18(1):61-79, 1988.

P. Eades, W. Lai, K. Misue, and K. Sugiyama. Preserving the Mental Map of a Diagram. In Proc. Compugraphics `91, pages 24-33, 1991.

K. Misue, P. Eades, W. Lai, and K. Sugiyama. Layout Adjustment and the Mental Map. J. of Visual Languages and Computing, pages 183-210, June 1995.

M-A. D. Storey and H.A. Müller. Graph layout adjustment strategies. Proc. of Graph Drawing '95. Springer, LNCS, vol. 1027, pages 487-499, 1995.

M.R. Garey and D.S. Johnson. Computers and Itractability: A Guide to hte theory of NP-Completeness. W.H. Freeman and company, NY, 1979.