Tech Report CS-96-22

The Rectangle of Influence Drawability Problem

G. Liotta, A. Lubiw H. Meijer and S. H. Whitesides

June 1996

Abstract:

A proximity drawing of a graph is a straight-line drawing where adjacent vertices are represented by points that are deemed to be close according to some proximity measure. A rectangle of influence drawing is a proximity drawing where the measure is based on the concept of rectangle of influence. Given two points u and v, the rectangle of influence of u and v is the axis-aligned rectangle having u and v at opposite corners. The rectangle of influence drawing of a graph G is a proximity drawing of G such that (i) for each pair of adjacent vertices u,v of G, the rectangle of influence of the points representing u and v is empty (i.e. contains no point representing a vertex distinct from u and v), and (ii) for each pair of non-adjacent vertices u,v of G, the rectangle of influence of the points representing u and v is not empty. Two different representation models are possible depending on whether the rectangle of influence is an open or a closed set.

In this paper we study the drawability of several classes of graphs with respect to both the closed and the open model. We characterize, for each class and model, which graphs have a rectangle of influence drawing. For each class we show that testing whether a graph G has a rectangle of influence drawing can be done in O(n) time, where n is the number of vertices of G. Furthermore, if the test for G is affirmative, we show how to construct a rectangle of influence drawing of G. All the drawing algorithms can be implemented so that they (1) produce drawings with all vertices placed at intersection points of an integer grid of size O($n^2$), (2) perform arithmetic operations on integers only, and (3) run in O(n) time, where n is the number of vertices of the input graph.

(complete text in pdf or gzipped postscript)