New Results on a Visibility Representation of Graphs in 3D

Fekete, Sándor P. and Houle, Michael E. and Whitesides, Sue (1996) New Results on a Visibility Representation of Graphs in 3D. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995 , pp. 234-241(Official URL: http://dx.doi.org/10.1007/BFb0021807).

Full text not available from this repository.

Abstract

This paper considers a 3-dimensional visibility representation of cliques K_n. In this representation, the objects representing the vertices are 2-dimensional and lie parallel to the x, y-plane, and two vertices of the graph are adjacent if and only if their corresponding objects see each other by a line of sight parallel to the z-axis that intersects the interiors of the objects. In particular, we represent vertices by unit discs and by discs of arbitrary radii (possibly different for different vertices); we also represent vertices by axis-aligned unit squares, by axis-aligned squares of arbitrary size (possibly different for different vertices), and by axis-aligned rectangles. We present: - a significant improvement (from 102 to 55) of the best known upper bound for the size of cliques representable by retrangles or squares of arbitrary size; - a sharp bound for the representation of cliques by unit squares (K_7 can be represented but K_n for n>7 cannot); - a representation of K_n by unit discs.

Item Type: Conference Paper
Additional Information: 10.1007/BFb0021807
Classifications: P Styles > P.900 Visibility
P Styles > P.060 3D
URI: http://gdea.informatik.uni-koeln.de/id/eprint/136

Actions (login required)

View Item View Item