A Visibility Representation for Graphs in Three Dimensions

Abstract

This paper proposes a 3-dimensional visibility representation of graphs G =( V;E) in which vertices are mapped to rectangles floating in R 3 parallel to the x;y-plane, with edges represented by vertical lines of sight. We apply an extension of the Erd} os-Szekeres Theorem in a geometric setting to obtain an upper bound of n = 56 for the largest representable complete graph Kn. On the other hand, we show by construction that n 22. These are the best existing bounds. We also note that planar graphs and complete bipartite graphs Km;n are representable, but that the family of representable graphs is not closed under graph minors.