Accession Number : ADA318040

Title :   The Rectangle of Influence Drawability Problem.

Descriptive Note : Technical rept.,

Corporate Author : BROWN UNIV PROVIDENCE RI DEPT OF COMPUTER SCIENCE

Personal Author(s) : Liotta, G. ; Lubiw, A. ; Meijer, H. ; Whitesides, S. H.

PDF Url : ADA318040

Report Date : 1996

Pagination or Media Count : 33

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 axle 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 (1) 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 (2) 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 dasses of graphs with respect to both the closed and the open model. We characterise, 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(n2), (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.

Descriptors :   *GRAPHS, *LINES(GEOMETRY), ALGORITHMS, INPUT, MODELS, GRIDS, APPLIED MATHEMATICS, NUMBERS, ARITHMETIC, ENGINEERING DRAWINGS.

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE