On a Visibility Representation of Graphs

Cobos, F. J. and Dana, J. C. and Hurtado, F. and Márquez, Alberto and Mateos, F. (1996) On a Visibility Representation of Graphs. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 152-161 (Official URL: http://dx.doi.org/10.1007/BFb0021799).

Full text not available from this repository.

Abstract

We give a visibility representation of graphs which extends some very well-known representations considered extensively in the literature. Concretely, the vertices are represented by a collection of parallel hyper-rectangles in R^n and the visibility is orthogonal to those hyper-rectangles. With this generalization, we can prove that each graph admits a visibility representation. But, it arises the problem of determining the minimum Euclidean space where such representation is possible. We consider this problem for concrete well-known families of graphs such as planar graphs, complete graphs and complete bipartite graphs.

Item Type:Conference Paper
Additional Information:10.1007/BFb0021799
Classifications:G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.900 Visibility
G Algorithms and Complexity > G.560 Geometry
ID Code:139

Repository Staff Only: item control page

References

H. Alt, M. Godau and S. Whitesides. Universal 3-Dimensional Visibility Representations for Graphs. Abstract presented at Graph Drawing'95, Passau (Germany).

S. Bellantoni, I. Ben-Arroyo Hartman, T. Przytycka and S. Whitesides. Grid intersection graphs and boxicity. North-Holland. Discrete Mathematics, 114:41-49, 1993.

P. Bose, H. Everett, S. Fekete, A. Lubiw, H. Meijer, K. Romanik, T. Shermer and S. Whitesides. On a Visibility Representation for Graphs in Three Dimensions. In David Avis and Prosenjit Bose, editors, Snapshots in Computational and Discrete Geometry, Volume III, McGill University, July 1994. Technical Report SOCS-94.50.

F. R. K. Chung. On unimodal subsequences. J. Combinatorial Theory, Series A, v. 29:267-279, 1980.

P. Erdös and A. Szekeres. A combinatorial problem in geometry. Compositio Mathematica, v. 2:463-470, 1935.

S. P. Fekete, M. E. Houle and S. Whitesides. New Results on a Visibility Representation of Graphs in 3D. Abstract presented at Graph Drawing'95, Passau (Germany). 1995.

M. Garey, D. Jhonson and H. So. An application of graph coloring to printed circuit testing. IEEE Trans. Circuits and Systems., CAS-23:591-598, 1976.

M. Y. Hsueh and D. O. Pederson. Computer-aided layout of LSI circuit bulding bloks. Proc. IEEE Int. Symp. on Circuits and Systems., pages 474-477, 1979.

J. Kratochvil and T. Przytycka. Grid intersection graphs and boxicity on surfaces. Abstract presented at Graph Drawing'95, Passau (Germany), 1995.

K. Kuratowski. Sur le problème des courbes gauches en topologie. Fund. Math., 15:271-283, 1930.

E. Lodi and L. Pagli. A VLSI algorithm for a visibility problem. In P. Bertolazzi and F. Luccio, editors, VLSI: Algorithms and Architectures, pages 125-134. North-Holland, Amsterdam, 1985.

S. L. Mitchell. Linear algorithms to recognize outerplanar and maximal outerplanar graphs. Information Processing Letters, 9(5):229-232, 1979.

M. Schlag, F. Luccio, P. Maestrini, D. T. Lee and C. K. Wong. A visibility problem in VLSI layout compaction. In F. P. Preparata, editor, Advances in Computing Research, volume 2, pages 259-282. JAI Press Inc, Greenwich. CT., 1985.

R. Tamassia and I. G. Tollis. A unified approach to visibility representations of planar graphs. Discrete and Computational Geometry, 1:321-341, 1986.

S. Wimer, I. Koren and I. Cederbaum. Floorplans, planar graphs and layouts. IEEE Trans. Circuits ans Systems, 35:267-278, 1988.

S. K. Wismath. Characterizing bar line-of-sight graphs. Proc. ACM Symp. on Computational Geometry. Baltimore. MD. 1985