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.
G., L., R., T., I. G., T., Vocca, P. (1997). Area requirement of Gabriel drawings. In D.P.B. Giancarlo Bongiovanni (a cura di), Algorithms and Complexity: Third Italian Conference, CIAC'97, Rome, Italy, March 12-14, 1997: Proceedings (pp. 135-146). Berlin, Heidelberg : Springer [10.1007/3-540-62592-5_67].
Area requirement of Gabriel drawings
VOCCA P
1997-01-01
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 | Dimensione | Formato | |
|---|---|---|---|
|
pentagon.pdf
non disponibili
Tipologia:
Documento in Post-print
Licenza:
Copyright dell'editore
Dimensione
222.42 kB
Formato
Adobe PDF
|
222.42 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
