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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/245

Actions (login required)

View Item View Item