
130 CHAPTER 4. PROXIMITY DRAWINGS
that the number of edges of an n-vertex graph that has a relative neighborhood drawing
in 3-dimensional space is O(n
4/3
). Chazelle, Edelsbrunner, Guibas, Hershberger, Seid e l,
and Sharir [CEG
+
94] showed that the maximum number of edges of an n-vertex graph
that has a Gabriel drawing in d-dimensional space (d ≥ 3) is Ω(n
2
). I n [MS80], [Tou80],
and [Lan69], the p lanar ity of Gabriel drawable graphs, relative neighborhood graphs, and
relatively closest drawable graphs were shown, respectively. Furthermore, in [Cim92] it was
shown that a cycle with thr ee vertices is not relatively closest dr awable.
Particular atte ...