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.
This work was performed while the first author was working at, and the third author was consulting with Tom Sawyer Software. It was, in part, funded by the NIST under grant number 70NANB5H1162. This paper is part of a series about the orthogonal library of the Graph Layout Toolkit produced by Tom Sawyer Software. Patent on these and related results is pending.
These results are part of a Ph.D thesis of the first author at Rutgers University under the supervision of Prof. Endre Boros.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
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 Computer Science, pages 124–135. Springer Verlag, 1994.
T. Biedl and M. Kaufmann. Static and incremental high-degree orthogonal drawings. In 5th European Symposium on Algorithms, Lecture Notes in Computer 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 aesthetic 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 Computer Science. Springer Verlag, 1995.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Biedl, T.C., Madden, B.P., Tollis, I.G. (1997). The three-phase method: A unified approach to orthogonal graph drawing. In: DiBattista, G. (eds) Graph Drawing. GD 1997. Lecture Notes in Computer Science, vol 1353. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63938-1_84
Download citation
DOI: https://doi.org/10.1007/3-540-63938-1_84
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63938-1
Online ISBN: 978-3-540-69674-2
eBook Packages: Springer Book Archive