Logo

Login

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. [Conference Paper]

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
Classifications:G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.070 Area / Edge Length
ID Code:245
Deposited By:Arnopolina, Galina
Deposited On:09 Nov 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=1547&spage=183

Repository Staff Only: item control page

References

1. 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.

2. 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.

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

4. 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.

5. 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.

6. 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.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.