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 2)-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 2)-time heuristic algorithm for the problem that finds a layout with smaller area than Misue’s.
Chapter PDF
Similar content being viewed by others
References
G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis, “Algorithms for drawing graphs: an annotated bibliography,” Computational Geometry Theory and Applications, vol. 4, pp. 235–282, 1994.
R. Tamassia, G. Di Battista, and C. Batini, “Automatic graph drawing and readability of diagrams,” IEEE Trans. on System, Man and Cybernetics, vol. 18, no. 1, pp. 61–79, 1988.
P. Eades, W. Lai, K. Misue, and K. Sugiyama, “Preserving the mental map of a diagram,” Proc. of COMPUGRAPHICS’ 91, pp. 34–43, 1991.
K. Misue, P. Eades, W. Lai, and K. Sugiyama, “Layout adjustment and the mental map,” Journal of Visual Languages and Computing, vol. 6, pp. 183–210, 1995.
M-A. D. Storey and H. A. Müller, “Graph layout adjustment strategies,” Proc. Graph Drawing’ 95, LNCS 1027, pp. 487–499. Springer-Verlag, 1995.
M. R. Garey and D. S. Johnson, “Computers and Intractability-A Guide to the Theory of NP-Completeness,” W. H. Freeman and Company, New York, 1979.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hayashi, K., Inoue, M., Masuzawa, T., Fujiwara, H. (1998). A Layout Adjustment Problem for Disjoint Rectangles Preserving Orthogonal Order. In: Whitesides, S.H. (eds) Graph Drawing. GD 1998. Lecture Notes in Computer Science, vol 1547. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-37623-2_14
Download citation
DOI: https://doi.org/10.1007/3-540-37623-2_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65473-5
Online ISBN: 978-3-540-37623-1
eBook Packages: Springer Book Archive