Logo

Login | Create Account

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). [Conference Paper]

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
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
ID Code:220
Deposited By:Selbach, Anna
Deposited On:19 Jan 2005
Last Modified:18 Sep 2008 13:08

Repository Staff Only: item control page

References

J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. Elsevier Science, New York, 1976.

P. Bose, W. Lenhart, and G. Liotta. Characterizing Proximity Trees. Algorithmica: Special Issue on Graph Drawing (to appear). Also available as TR-SOCS 93.9, School of Computer Science, McGill Univ., 1993.

P. Bose. G. Di Battista, W. Lenhart, and G. Liotta. Proximity Constraints and Representable Trees. Proc. GD'94, 1994.

R. J. Cimikowsky. Properties of Some Euclidean Proximity Graphs. Patt. Recogn. Letters, 13, 1992, pp. 417-423.

M. de Berg, S. Carlsson, and M.H. Overmars. A General Approach to Dominance in the Plane. J. of Algorithms, 13, 1992, pp. 274-296.

G. Di Battista, P. Eades, R. Tamassia and I.G. Tollis. Algorithms for Automatic Graph Drawing: An Annotated Bibliography. Computational Geometry: Theory and Applications (to appear).

G. Di Battista, W. Lenert, G. Liotta. Proximity Drawability: a Survey. Proc. GD'94, 1994.

G. Di Battista and L. Vismara. Angles of Planar Triangular Graphs. Proc. STOC'93, 1993, pp.431-437.

M. B. Dillencourt and W. D. Smith. Graph-Theoretical Conditions for Inscribability and Delaunay Realizability. Proc. CCCG'94, 1994, pp. 287-292.

P. Eades and S. Whitesides. The Realization Problem for Euclidean Minimum Spanning Tree is NP-hard. Proc. ACM Symp. on Comp. Geom., pp. 49-56, 1994.

H. de Fraysseix, J. Pach, and R. Pollack. Smal Sets Supporting Fary Embeddings of Planar Graphs. Proc. STOC'88, 1988, pp. 426-433.

H. de Fraysseix, J. Pach, and R. Pollack. How to Draw a Planar Graph on a Grid. Combinatorica, 10, 1990, pp. 41-51.

M. Ichino, J. Sklansky. The Realive Neighborhood Graph for Mixed Feature Variables. Patt. Recogn., 18, 1985, pp. 161-167.

J. W. Jaromczyk and G. T. Taussaint. Relative Neighborhood Graphs and Their Relatives. Proc. of the IEEE, 80, 1992, pp. 1502-1517.

G. Kant. Drawing Planar Graphs Using the lmc-ordering. Proc. FOCS '92, 1992, pp. 101-110.

D. G. Kirkpatrick and J. D. Radke. A Framework for Computational Morphology. Computational Geometry, ed. G. T. Toussaint, Elsevier, Amsterdam, 1985, pp. 217-248.

P. M. Lankford. Regionalization: Theory and Alternative Algorithms. Geogr. Anal., 1, 1969, pp. 196-212.

A. Lubiw and N. Sleumer. All Maximal Outerplanar Graphs are Relative Neighborhood Graphs. Proc. CCCG '93, 1993, pp. 198-203.

D. W. Matula and R. R. Socal. Properties of Gabriel Graphs Relevant to Geographic Variation Research and the Clustering of Points in the Plane. Geogr. Anal., 12, 1980, pp. 205-222.

M. H. Overmars and D. Wood. On Rectangular Visibility. Journal of Algorithms, 9, 1988, pp. 372-390.

M. S. Paterson and F. F. Yao, On Nearest-Neighbor Graphs. Proc. ICALP '92, 1992, pp. 416-426.

F. P. Preparata and M. I. Shamos, Computational Geometry: an Introduction. Springer-Verlag, New York, 1985.

J. D. Radke. On the Shape of a Set of Points. Computational Morphology, ed. G. T. Toussaint, Elsevier, Amsterdam, 1988, pp. 105-136.

G. T. Toussaint. The Relative Neighborhood Graph of a Finite Planar Set. Patt. Recogn., 1980, pp. 261-268.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.