The Three-Phase Method: A Unified Approach to Orthogonal Graph Drawing

Biedl, Therese and Madden, Brendan and Tollis, Ioannis G. (1998) The Three-Phase Method: A Unified Approach to Orthogonal Graph Drawing. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 391-402 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_84).

Full text not available from this repository.

Abstract

In this paper, we study orthogonal graph drawings from a practical point of view. Most previously existing algorithms restricted the attention to graphs of maximum degree four. Here we study orthogonal drawing algorithms that work for any input graph, and discuss different models for such drawings. Then we introduce the three-phase method, a generic technique to create high-degree orthogonal drawings. This approach simplifies the description and implementation of orthogonal graph drawing, and can be applied to global as well as interactive and incremental settings.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_84
Classifications:M Methods > M.300 Dynamic / Incremental / Online
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:152

Repository Staff Only: item control page

References

T. Biedl. Orthogonal Graph Visualization: The Three-Phase Method With Applications. PhD thesis, RUTCOR, Rutgers University, May 1997.

T. Biedl and G. Kant. A better heuristic for orthogonal graph drawings. In 2nd European Symposium on Algorithms, volume 855 of Lecture Notes in Compuetr Science, pages 124-135. Springer Verlag, 1994.

T. Biedl and M. Kaufmann. Static incremental high-degree orthogonal drawings. In 5th European Symposium on Algorithms, Lecture Notes in Compuetr Science. Springer Verlag, 1997. To appear.

F. Brandenburg, editor. Symposium on Graph Drawing 95, volume 1027 of Lecture Notes in Computer Science. Springer Verlag, 1996.

G. Di Battista, P. Eades, R. Tamassia, and I. Tollis. Algorithms for drawing graphs: an annotated bibliography. Comp. Geometry: Theory and Applications, 4(5):235-282, 1994.

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

U. Fößmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In Brandenburg [4], pages 254-266.

G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4-32, 1996.

T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Teubner/Wiley & Sons, Stuttgart/Chicester, 1990.

K. Miriyala, S. Hornick, and R. Tamassia. An incremental approach to aeesthetic graph layout. In 6th Intl. IEEE. Workshop Computer-Aided Software Eng.. 1993.

K. Misue, P. Eades, W. Lai, and K. Sugiyama. Layout adjustment and the mental map. J. Visual Languages and Computing, pages 183-210, June 1995.

S. North, editor. Symposium on Graph Drawing 96, volume 1190 of Lecture Notes in Computer Science. Springer Verlag, 1997.

A. Papakostas, J.M. Six, and I. Tollis. Experimental and theoretical results in interactive orthogonal graph drawing. In North [12], pages 371-386.

A. Papakostas and I. Tollis. Issues in interactive orthogonal graph drawing. In Brandenburg [4], pages 419-430.

A. Papakostas and I. Tollis. High-degree orthogonal drawings with small grid-size and few bends. In 5th Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science. Springer Verlag. 1997. To appear.

A. Papakostas and I. Tollis. A pairing technique for area-efficient orthogonal drawings. In North [12], pages 355-370.

P. Rosenstiehl and R.E. Tarjan. Rectilinear planar layouts and bipolar orientation of planar graphs. Discrete Computational Geometry, 1:343-353, 1986.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM Journal of Computing, 16(3): 421-444, 1987.

R. Tamassia, G. Di Battista, and C. Batini. Automatic graph drawing and readability of diagrams. IEEE Trans. Systems, Man and Cybernetics, 18(1), 1988.

R. Tamassia and I. Tollis. A unified approach to visibility representations of planar graphs. Discrete Computational Geometry, 1:321-341, 1986.

R. Tamassia and I. Tollis, editors. DIMACS International Workshop, Graph Drawing 94, volume 894 of Lecture Notes in 1. Computer Science. Springer Verlag, 1995.