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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/376

Actions (login required)

View Item View Item