Tech Report CS-96-29

Area Requirement of Gabriel Drawings

G. Liotta, R. Tamassia, I. G. Tollis and Paola Vocca

October 1996

Abstract:

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.

(complete text in pdf or gzipped postscript)