We introduce a novel technique for drawing proximity graphs in polynomial area and volume. Previously known algorithms produce representations whose size increases exponentially with the size of the graph. This holds even when we restrict ourselves to binary trees. Our method is quite general and yields the first algorithms to construct polynomial area weak Gabriel drawings of ternary trees, polynomial area weak \beta-proximity drawing of binary trees for any 0 =< \beta < \infty, and polynomial volume weak Gabriel drawings of unbounded degree trees. Notice that, in general, the above graphs do not admit a strong proximity drawing. Finally, we give evidence of the effectiveness of our technique by showing that a class of graph requiring exponential area even for weak Gabriel drawings, admits a linear volume strong \beta-proximity drawing and a relative neighborhood drawing. All the algorithms described run in linear time.

Proximity Drawings in Polynomial Area and Volume

VOCCA, PAOLA
2004-01-01

Abstract

We introduce a novel technique for drawing proximity graphs in polynomial area and volume. Previously known algorithms produce representations whose size increases exponentially with the size of the graph. This holds even when we restrict ourselves to binary trees. Our method is quite general and yields the first algorithms to construct polynomial area weak Gabriel drawings of ternary trees, polynomial area weak \beta-proximity drawing of binary trees for any 0 =< \beta < \infty, and polynomial volume weak Gabriel drawings of unbounded degree trees. Notice that, in general, the above graphs do not admit a strong proximity drawing. Finally, we give evidence of the effectiveness of our technique by showing that a class of graph requiring exponential area even for weak Gabriel drawings, admits a linear volume strong \beta-proximity drawing and a relative neighborhood drawing. All the algorithms described run in linear time.
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11587/103274
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact