Bose, Prosenjit; Everett, Hazel; Fekete, Sándor P.; Houle, Michael E.; Lubiw, Anna; Meijer, Henk; Romanik, Kathleen; Rote, Günter; Shermer, Thomas C.; Whitesides, Sue; Zelle, Christian A visibility representation for graphs in three dimensions. (English) Zbl 0895.68111 J. Graph Algorithms Appl. 2, Paper No. 3, 16 p. (1998). Summary: This paper proposes a 3-dimensional visibility representation of graphs \(G= (V,E)\) in which vertices are mapped to rectangle floating in \(\mathbb{R}^3\) parallel to the \(x,y\)-plane, 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 \(n=56\) for the largest representable complete graph \(K_n\). On the other hand, we show by construction that \(n\geq 22\). These are the best existing bounds. We also note that planar graphs and complete bipartite graphs \(K_{m,n}\) are representable, but that the family of representable graphs is not closed under graph minors. Cited in 1 ReviewCited in 17 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 05C99 Graph theory Keywords:visibility representation of graphs PDFBibTeX XMLCite \textit{P. Bose} et al., J. Graph Algorithms Appl. 2, Paper No. 3, 16 p. (1998; Zbl 0895.68111) Full Text: DOI EuDML