Area Requirement of Gabriel Drawings
Giuseppe Liotta, Roberto Tamassia, Ioannis G. Tollis, Paola Vocca · 1996
In this paper we investigate the area requirement of proximity drawings and we prove an exponential lower bound. Namely, our main contribution is to show the existence of a class of Gabriel-drawable graphs that require exponential area for any Gabriel drawing and any resolution rule. Also, we extend the result to an infinite class of proximity drawings.