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


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.
  PostScript file 2.15 MByte (gzipped, 238 kBytes) pdf file (gzipped)
other papers about this subject