×

A visibility representation for graphs in three dimensions. (English) Zbl 0895.68111

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.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C99 Graph theory
PDFBibTeX XMLCite
Full Text: DOI EuDML