Recognizing Rectangle of Influence Drawable Graphs (extended abstract)

ElGindy, H. and Liotta, Giuseppe and Lubiw, Anna and Meijer, Henk and Whitesides, Sue (1995) Recognizing Rectangle of Influence Drawable Graphs (extended abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 352-363(Official URL: http://dx.doi.org/10.1007/3-540-58950-3_390).

Full text not available from this repository.

Abstract

Given two points x and y in the plane the rectangle of influence of x and y is the axis-aligned rectangle having x and y at opposite corners. The rectangle of influence drawing of a graph G is a Straight-line 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. does not contain any other point representing any other vertex of G except possibly the two representing 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. In this paper we consider several classes of graphs, and we characterize, for each class, which graphs of the class have a rectangle of influence drawing. For each class we show that the problem of testing whether a graph G has a rectangle of influence drawing can be done in linear time. Furthermore, if the test for G is affirmative, a rectangle of influence drawing of G can be constructed in linear time with the real RAM model of computation.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-58950-3_390
Classifications: P Styles > P.720 Straight-line
Z Theory > Z.250 Geometry
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.560 Geometry
P Styles > P.999 Others
URI: http://gdea.informatik.uni-koeln.de/id/eprint/220

Actions (login required)

View Item View Item