Volume Requirements of 3D Upward Drawings

Di Giacomo, Emilio and Liotta, Giuseppe and Meijer, Henk and Wismath, Stephen, K. (2006) Volume Requirements of 3D Upward Drawings. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 101-110 (Official URL: http://dx.doi.org/10.1007/11618058_10).

Full text not available from this repository.

Abstract

This paper studies the problem of drawing directed acyclic graphs in three dimensions in the straight-line grid model, and 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 special case of rooted trees a linear volume upper bound is achievable .

Item Type:Conference Paper
Additional Information:10.1007/11618058_10
Classifications:P Styles > P.840 Upward
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.060 3D
ID Code:716

Repository Staff Only: item control page

References

P. Bertolazzi, G. Di Battista, G. Liotta, and C. Mannino. Upward drawings of triconnected digraphs. Algorithmica, 6(12):476-497, 1994.

P. Bertolazzi, G. Di Battista, C. Mannino, and R. Tamassia. Optimal upward planarity testing of single-source digraphs. SIAM J. Computing, 27(1):132-169, 1998.

P. Bose, J.Czyzowicz, P. Morin, and D. R. Wood. The maximum number of edges in a three-dimensional grid-drawing. J. of Graph Algorithms and Applications, 8(1):21-26, 2004.

T. Calamoneri and A. Sterbini. 3D straight-line grid drawing of 4-colorable graphs. Information Processing Letters, 63(2):97-102, 1997.

R. F. Cohen, P. Eades, T. Lin, and F. Ruskey. Three-dimensional graph drawing. Algorithmica, 17(2):199-208, 1997.

G. Di Battista, R. Tamassia, and I. G. Tollis. Area requirement and symmetry display of planar upward drawings. Discrete and Computational Geometry, 7:381-401, 1992.

E. Di Giacomo. Drawing series-parallel graphs on restricted integer 3D grids. In G. Liotta, editor, Proc. of 11th International Symposium on Graph Drawing, GD 2003, volume 2912 of Lecture Notes Computer Science, pages 238-246. Springer-Verlag, 2004.

E. Di Giacomo, G. Liotta, and H. Meijer. Computing straight-line 3D grid drawings of graphs in linear volume. Computational Geometry. to appear.

V. Dujmovic, P. Morin, and D. R. Wood. Layout of graphs with bounded tree-width. SIAM J. on Computing, 34(3):553-579, 2005.

V. Dujmovic, A. Por, and D. R. Wood. Track layouts of graphs. Discrete Math. Theor. Comput. Sci., 6(2):497-522, 2004.

V. Dujmovic and D. R. Wood. Layouts of graphs subdivisions. In J. Pach, editor, Proc. 12th International Symposium on Graph Drawing, GD 2004, volume 3383 of Lecture Notes in Computer Science, pages 133-143, Springer, 2004.

V. Dujmovic and D. R. Wood. Three-dimensional grid drawings with sub-quadratic volume. In J. Pach, editor, Towards a Theory of Geometric Graphs, volume 342, pages 55-66. 2004.

S. Felsner, G. Liotta, and S. K. Wismath. Straight-line drawings on restricted integer grids in two and three dimensions. J. of Graph Algorithms and Applications, 7(4):363-398, 2003.

A. Garg and R. Tamassia. On the computational complexity of upward and rectilinear planarity testing. SIAM J. Computing, 31(2):601-625, 2001.

L. S. Heath and S. V. Pemmaraju. Stack and queue layouts of posets. SIAM J. on Discrete Mathematics, 10:599-625, 1997.

L. S. Heath and S. V. Pemmaraju. Stack and queue layouts of directed acyclic graphs: Part II. SIAM J. on Computing, 28:1588-1626, 1999.

L. S. Heath, S. V. Pemmaraju, and A. Trenk. Stack and queue layouts of directed acyclic graphs: Part I. SIAM J. on Computing, 28:1510-1539, 1999.

M. D. Hutton and A. Lubiw. Upward planning of single-source acyclic digraphs. SIAM J. on Computing, 25(2):291-311, 1996.

T. Poranen. A new algorithm for drawing series-parallel digraphs in 3D. Technical Report A-2000-16, Dept. of Computer and Information Sciences, University of Tampere, Finland, 2000.