This paper studies the problem of drawing directed acyclic graphs in three dimensions in the straight-line grid model so that all directed edges are oriented in a common (upward) direction. We show that there exists a family of outerplanar directed acyclic graphs whose volume requirement is super-linear. We also prove that for the case of directed trees a linear-volume upper bound is achievable.
Volume Requirements of 3D Upward Drawings
DI GIACOMO, Emilio;LIOTTA, Giuseppe;
2009
Abstract
This paper studies the problem of drawing directed acyclic graphs in three dimensions in the straight-line grid model so that all directed edges are oriented in a common (upward) direction. We show that there exists a family of outerplanar directed acyclic graphs whose volume requirement is super-linear. We also prove that for the case of directed trees a linear-volume upper bound is achievable.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.
