Multi-dimensional Orthogonal Graph Drawing with Small Boxes(Extended Abstract)

Wood, David R. (1999) Multi-dimensional Orthogonal Graph Drawing with Small Boxes(Extended Abstract). In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 311-322 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_32).

Full text not available from this repository.

Abstract

In this paper we investigate the general position model for the drawing of arbitrary degree graphs in the D-dimensional (D \ge 2) orthogonal grid. In this model no two vertices lie in the same grid hyperplane. We show that for D \ge 3, given an arbitrary layout and initial edge routing a crossing-free orthogonal drawing can be determined. We distinguish two types of algorithms. Our layout-based algorithm, given an arbitrary fixed layout, determines a degree-restricted orthogonal drawing with each vertex having aspect ratio two. Using a balanced layout this algorithm establishes improved bounds on the size of vertices for 2-D and 3-D drawings. Our routing-based algorithm produces 2-degree-restricted 3-D orthogonal drawings. One advantage of our approach in 3-D is that edges are typically routed on each face of a vertex; hence the produced drawings are more truly three-dimensional than those produced by some existing algorithms.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_32
Classifications:G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.420 Crossings
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
P Styles > P.999 Others
ID Code:359

Repository Staff Only: item control page

References

T. Biedl and M. Kaufmann. Area-efficient static and incremental graph drawings. In R. Burkhard and G. Woeginger, editors, Proc. Algorithms: 5th Annual European Symp. (ESA '97), volume 1284 of Lecture Notes in Comput. Sci., pages 37-52, Berlin, 1997. Springer.

T. Biedl, B. Madden, and I. G. Tollis. The three-phase method: A unified approach to orthogonal graph drawing. In Di Battista [5], pages 391-402.

T. Biedl, T. Shermer, S. Whitesides, and S. Wismath. Orthogonal 3-D graph drawing. In Di Battista [5], pages 76-86.

T. C. Biedl. Three approaches to 3D-orthogonal box-drawings. In Whitesides [20], pages 30-43.

G. Di Battista, editor. Proc. Graph Drawing: 5th International Symp. (GD '97), volume 1353 of Lecture Notes in Comput. Sci., Berlin, 1998. Springer.

G. Di Battista, W. Didimo, M. Patrignani, and M. Pizzonia. Orthogonal and quasi-upward drawings with vertices of arbitrary size. In J. Kratochvíl, editor, Proc. Graph Drawing: 7th International Symp. (GD '99), Lecture Notes in Comput. Sci., Berlin. Springer. to appear.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, New Jersey, 1999.

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of four graph drawing algorithms. Comput. Geom., 7(5-6):303-325, 1997.

W. Didimo and G. Liotta. Computing orthogonal drawings in a variable embedding setting. In K.-Y. Chwa and O. H. Ibarra, editors, Proc. Algorithms and Computation (ISAAC '98), volume 1533 of Lecture Notes in Comput. Sci., pages 79-88, Berlin, 1998. Springer.

P. Eades, A. Symvonis, and S. Whitesides. Two algorithms for three dimensional orthogonal graph drawing. In North 16, pages 139-154.

P. Eades, A. Symvonis, and S. Whitesides. Three dimensional orthogonal graph drawing algorithms. 1998. submitted.

S. Even and G. Garnot. Grid layouts of block diagrams - bounding the number of bends in each connection. In R. Tamassia and I. G. Tollis, editors, Proc. Graph Drawing: DIMACS International Workshop (GD'94), volume 894 of Lecture Notes in Comput. Sci., pages 64-75, Berlin, 1995. Springer.

U. Fößmeier, G. Kant, and M. Kaufmann. 2-visibility drawings of planar graphs. In North [16], pages 155-158.

U. Fößmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In F. J. Brandenburg, editor, Proc. Graph Drawing: Symp. on Graph Drawing (GD '95), volume 1027 of Lecture Notes Comput. Sci., pages 254-266, Berlin, 1996. Springer.

U. Fößmeier and M. Kaufmann. Algorithms and area bounds for nonplanar orthogonal drawings. In Di Battista [5], pages 134-145.

S. North, editor. Proc. Graph Drawing: Symp. on Graph Drawing (GD '96), volume 1190 of Lecture Notes in Comput. Sci., Berlin, 1997. Springer.

A. Papakostas and I. G. Tollis. Orthogonal drawing of high degree graphs with small area and few bends. In F. Dehne, A. Rau-Chaplin, J.-R. Sack, and R. Tamassia, editors, Proc. Algorithms and Data Structures: 5th International Workshop (WADS'97), volume 1272 of Lecture Notes in Comput. Sci., pages 354-367, Berlin, 1997. Springer.

A. Papakostas and I. G. Tollis. Incremental orthogonal graph drawing in three dimensions. In Di Battista [5], pages 52-63.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput., 16(3):421-443, June 1987.

S. Whitesides, editor. Proc. Graph Drawing: 6th International Symp. (GD '98), volume 1547 of Lecture Notes in Comput. Sci. Springer, 1998.

D. R. Wood. An algorithm for three-dimensional orthogonal graph drawing. In Whitesides [20], pages 332-346.

D. R. Wood. Multi-dimensional orthogonal graph drawing in the general position model. Technical Report 99/38, School of Computer Science and Software Engineering, Monash University, Australia, 1999. (available at http://www.csse.monash.edu.au/publications/).

D. R. Wood. A new algorithm and open problems in three-dimensional orthogonal graph drawing. In R. Raman and J. Simpson, editors, Proc. Australasian Workshop on Combinatorial Algorithms (AWOCA '99), pages 157-167. Curtin University of Technology, Perth, 1999.