SpringerLink

Lecture Notes in Computer Science, 2003, Volume 2607/2003, 26-37, DOI: 10.1007/3-540-36494-3_4

Rectangle Visibility Graphs: Characterization, Construction, and Compaction

Ileana Streinu and Sue Whitesides

View Related Documents

Abstract

Non-overlapping axis-aligned rectangles in the plane define visibility graphs in which vertices are associated with rectangles and edges with visibility in either the horizontal or vertical direction. The recognition problem for such graphs is known to be NP-complete. This paper introduces the topological rectangle visibility graph.We give a polynomial time algorithm for recognizing such a graph and for constructing, when possible, a realizing set of rectangles on the unit grid. The bounding box of these rectangles has optimum length in each dimension. The algorithm provides a compaction tool: given a set of rectangles, one computes its associated graph, and runs the algorithm to get a compact set of rectangles with the same visibility properties.
Partially supported by NSF RUI grant CCR-0105507.
Partially supported by NSERC and FCAR.

Fulltext Preview

Image of the first page of the fulltext document