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.