×

Universal 3-dimensional visibility representations for graphs. (English) Zbl 0894.68103

Summary: This paper studies 3-dimensional visibility representations of graphs in which objects in 3-D correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which classes of simple objects are universal, i.e., powerful enough to represent all graphs. In particular, we show that there is no constant \(k\) for which the class of all polygons having \(k\) or fewer sides is universal. However, we show by construction that every graph on \(n\) vertices can be represented by polygons each having at most \(2n\) sides. The construction can be carried out by an \(O(n^2)\) algorithm. We also study the universality of classes of simple objects (translates of a single, not necessarily polygonal object) relative to cliques \(K_n\) and similarly relative to complete bipartite graphs \(K_{n,m}\).

MSC:

68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N., The number of polytopes, configurations and real matroids, Mathematica, 33, 62-71 (1986) · Zbl 0591.05014
[2] Alt, H.; Godau, M.; Whitesides, S., Universal 3-dimensional visibility representations for graphs, (Proceedings Symposium on Graph Drawing. Proceedings Symposium on Graph Drawing, Passau, Germany, 1995. Proceedings Symposium on Graph Drawing. Proceedings Symposium on Graph Drawing, Passau, Germany, 1995, Lecture Notes in Computer Science, 1027 (1995), Springer: Springer Berlin), 8-19
[3] Bose, P.; Everett, H.; Fekete, S.; Lubiw, A.; Meijer, H.; Romanik, K.; Shermer, T.; Whitesides, S., On a visibility representation for graphs in three dimensions, (Avis, D.; Bose, P., Snapshots of Computational and Discrete Geometry, Vol. 3 (July 1994)), 2-25, McGill University School of Computer Science Technical Report SOCS-94.50
[4] Dean, A.; Hutchinson, J., Rectangle-visibility representations of bipartite graphs, (Proceedings Graph Drawing, Princeton, NJ, 1994. Proceedings Graph Drawing, Princeton, NJ, 1994, Lecture Notes in Computer Science, 894 (1995), Springer: Springer Berlin), 159-166
[5] Di Battista, G.; Eades, P.; Tamassia, R.; Tollis, I. G., Algorithms for drawing graphs: an annotated bibliography, Computational Geometry: Theory and Applications, 4, 5, 235-282 (1994), Also available from wilma.cs.brown.edu by ftp · Zbl 0804.68001
[6] Erdös, P.; Szekeres, G., A combinatorial problem in geometry, Compositio Math., 2, 463-470 (1935) · Zbl 0012.27010
[7] Fekete, S.; Houle, M.; Whitesides, S., New results on a visibility representation of graphs in 3D, (Proceedings Symposium on Graph Drawing. Proceedings Symposium on Graph Drawing, Passau, Germany, 1995. Proceedings Symposium on Graph Drawing. Proceedings Symposium on Graph Drawing, Passau, Germany, 1995, Lecture Notes in Computer Science, 1027 (1995), Springer: Springer Berlin), 234-241
[8] S. Felsner, Personal communication, 1995.; S. Felsner, Personal communication, 1995.
[9] Grünbaum, B., On a conjecture of H. Hadwiger, Pacific J. Math., 11, 215-219 (1961) · Zbl 0131.20003
[10] Hadwiger, H., Über Treffanzahlen bei translationsgleichen Eikörpern, Arch. Math., VIII, 212-213 (1957) · Zbl 0080.15501
[11] Kranakis, E.; Krizanc, D.; Urrutia, J., On the number of directions in visibility representations of graphs, (Proceedings Graph Drawing, Princeton, NJ, 1994. Proceedings Graph Drawing, Princeton, NJ, 1994, Lecture Notes in Computer Science, 894 (1995), Springer: Springer Berlin), 167-176
[12] Romanik, K., Directed VR-representable graphs have unbounded dimension, (Proceedings Graph Drawing, Princeton, NJ, 1994. Proceedings Graph Drawing, Princeton, NJ, 1994, Lecture Notes in Computer Science, 894 (1995), Springer: Springer Berlin), 177-181
[13] Tamassia, R.; Tollis, I., A unified approach to visibility representations of planar graphs, Discrete Comput. Geom., 1, 321-341 (1986) · Zbl 0607.05026
[14] Wismath, S., Characterizing bar line-of-sight graphs, (Proceedings ACM Symp. on Computational Geometry (1985)), 147-152
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.