Prosenjit Bose, Hazel Everett, Sándor Fekete, Michael E. Houle,
Anna Lubiw, Henk Meijer, Kathleen Romanik, Günter Rote, Tom Shermer,
Sue Whitesides, and Christian Zelle:
A visibility representation for graphs in three dimensions
Journal of Graph Algorithms and
Applications 2, no. 3 (1998), 1–16. doi:10.7155/jgaa.00006
Abstract
We propose a 3-dimensional visibility representation of graphs in which
vertices are mapped to horizontal axis-parallel rectangles floating in
3-space, with edges represented by vertical lines of sight. We apply an
extension of the Erdös-Szekeres Theorem in a geometric setting to
obtain an upper bound of 56 for size of the largest complete graph which
is representable. On the other hand, we construct a representation of the
complete graph with 22 vertices. These are the best existing bounds.