Visibility Representations of Complete Graphs

Babilon, Robert and Nyklová, Helena and Pangrác, Ondrej and Vondrák, Jan (1999) Visibility Representations of Complete Graphs. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 333-340 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_34).

Full text not available from this repository.

Abstract

In this paper we study 3-dimensional visibility representations of complete graphs. The vertices are represented by equal regular polygons lying in planes parallel to the xy-plane. Two vertices are adjacent if and only if the two corresponding polygons see each other - i. e. it is possible to construct an abscissa perpendicular to the xy-plane connecting the two polygons and avoiding all the others. We give bounds for the maximal size f(k) of a clique represented by regular k-gons: \lfloor (k+1)/2 \rfloor + 2 \le f(k) \le 2^{2^{k}} and we present a particular result for triangles: f(3) \ge 14.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_34
Classifications:P Styles > P.900 Visibility
P Styles > P.060 3D
ID Code:376

Repository Staff Only: item control page

References

AGW. H. Alt, M. Godau, S. Whitesides: Universal 3-Dimensional Visibility Representations for Graphs. Proc. Graph Drawing '95, Passau, 1995. Lecture Notes in Computer Science LNCS #1027, Springer-Verlag, 1996, pp. 8-19

FHW. S. P. Fekete, M. E. Houle, S. Whitesides: New Results on a Visibility Representation of Graphs in 3D. Proc. Graph Drawing '95, Passau, 1995. Lecture Notes in Computer Science LNCS #1027, Springer-Verlag, 1996, pp. 234-241