In this paper, we investigate the volume, aspect ratio, angular resolution, edge-separation, and bit-requirement of crossing-free straight-line 3D drawings. We assume the vertex resolution rule, which requires minimum unit distance between any two vertices. Our main result shows that an N-vertex graph colorable with O(1) colors admits a crossing-free straight-line 3D drawing with O(N√N) volume, O(1) aspect ratio,gW(l/N O(1)) angular resolution, Ω (1/N O(1)) edge-separation, and O(log N) bit-requirement, which can be constructed in O(N) time.

Garg, A., Tamassia, R., Vocca, P. (1996). Drawing with colors. In M.S. Josep Diaz (a cura di), Algorithms - ESA '96: Fourth Annual European Symposium, Barcelona, Spain, September 25-27, 1996: proceedings (pp. 12-26). Berlin, Heidelberg : Springer [10.1007/3-540-61680-2_43].

Drawing with colors

VOCCA P
1996-01-01

Abstract

In this paper, we investigate the volume, aspect ratio, angular resolution, edge-separation, and bit-requirement of crossing-free straight-line 3D drawings. We assume the vertex resolution rule, which requires minimum unit distance between any two vertices. Our main result shows that an N-vertex graph colorable with O(1) colors admits a crossing-free straight-line 3D drawing with O(N√N) volume, O(1) aspect ratio,gW(l/N O(1)) angular resolution, Ω (1/N O(1)) edge-separation, and O(log N) bit-requirement, which can be constructed in O(N) time.
1996
Settore INFO-01/A - Informatica
English
Rilevanza internazionale
Articolo scientifico in atti di convegno
3D graph drawing
Straight line drawing
Garg, A., Tamassia, R., Vocca, P. (1996). Drawing with colors. In M.S. Josep Diaz (a cura di), Algorithms - ESA '96: Fourth Annual European Symposium, Barcelona, Spain, September 25-27, 1996: proceedings (pp. 12-26). Berlin, Heidelberg : Springer [10.1007/3-540-61680-2_43].
Garg, A; Tamassia, R; Vocca, P
Contributo in libro
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/2108/396807
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? ND
social impact