New Results on a Visibility Representation of Graphs in 3DFekete, 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 2022, 1995 , pp. 234241(Official URL: http://dx.doi.org/10.1007/BFb0021807). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/BFb0021807
AbstractThis paper considers a 3dimensional visibility representation of cliques K_n. In this representation, the objects representing the vertices are 2dimensional and lie parallel to the x, yplane, 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 zaxis 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 axisaligned unit squares, by axisaligned squares of arbitrary size (possibly different for different vertices), and by axisaligned 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.
Actions (login required)
