Rectangle of Influence Drawings of Graphs without Filled 3-Cycles

Biedl, Therese and Bretscher, Anna and Meijer, Henk (1999) Rectangle of Influence Drawings of Graphs without Filled 3-Cycles. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 359-368 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_37).

Full text not available from this repository.

Abstract

In this paper, we study rectangle of influence drawings, i. e., drawings of graphs such that for any edge the axis-parallel rectangle defined by the two endpoints of the edge is empty. Specifically, we show that if G is a planar graph without filled 3-cycles, i. e., a planar graph that can be drawn such that the interior of every 3-cycle is empty, then G has a rectangle of influence drawing.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_37
Classifications:M Methods > M.999 Others
P Styles > P.720 Straight-line
Z Theory > Z.250 Geometry
P Styles > P.900 Visibility
M Methods > M.600 Planar
P Styles > P.999 Others
ID Code:379

Repository Staff Only: item control page

References

N. Alon, Z. Füredi, and M. Katchalski. Separating pairs of points by standard boxes. European Journal of Combinatorics, 6:205-210, 1985.

T. Biedl, G. Kant, and M. Kaufmann. On triangulating planar graphs under the four-connectivity constraint. Algorithmica, 19(4):427-446, 1997.

J. Bondy and U. Murty. Graph Theory and Applications. American Elsevier Publishing Co., 1976.

M. de Berlin, S. Carlsson, and M. Overmars. A general approach to dominance in the plane. Journal of Algorithms, 13:274-296, 1992.

G. Di Battista, W. Lenhart, and G. Liotta. Proximinity drawability: A survey. In R. Tamassia and I. G. Tollis, editors, DIMACS International Workshop, Graph Drawing 94, volume 894 of Lecture Notes in Computer Science, pages 328-339. Springer-Verlag, 1995.

H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10:41-51, 1990.

M. Ichino and J. Sklansky. The relative neighborhood graph for mixed feature variables. Pattern Recognition, 18(2):161-167, 1985.

G. Liotta, A. Lubiw, H. Meijer, and S. Whitesides. The Rectangle of Influence drawability problem. Computational Geometry: Theory and Applications, 10(1):1-22, 1998.

M. H. Overmars and D. Wood. On rectangular visibility. Journal of Algorithms, 9(3):372-390, 1988.

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