The Rectangle of Influence Drawability Problem.
BROWN UNIV PROVIDENCE RI DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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 On 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 On2, 2 perform arithmetic operations on integers only, and 3 run in On time, where n is the number of vertices of the input graph.
- Numerical Mathematics