In this paper we investigate the area requirement of proximity drawings and we prove an exponential lower bound. 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. The result is further extended to an infinite class of proximity drawings.
Area requirement of Proximity Drawings
LIOTTA, Giuseppe;
1997
Abstract
In this paper we investigate the area requirement of proximity drawings and we prove an exponential lower bound. 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. The result is further extended to an infinite class of proximity drawings.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
