Refinement of Orthogonal Graph Drawings

Six, Janet M. and Kakoulis, Konstantinos G. and Tollis, Ioannis G. (1998) Refinement of Orthogonal Graph Drawings. In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 302-315 (Official URL: http://dx.doi.org/10.1007/3-540-37623-2_23).

Full text not available from this repository.

Abstract

Current orthogonal graph drawing algorithms produce drawings which are generally good. However, many times the readability of orthogonal drawings can be significantly improved with a postprocessing technique, called refinement, which improves aesthetic qualities of a drawing such as area, bends, crossings, and total edge length. Refinement is separate from layout and works by analyzing and then fine-tuning the existing drawing in an efficient manner. In this paper we define the problem and goals of orthogonal drawing refinement and introduce a methodology which efficiently refines any orthogonal graph drawing. We have implemented our technique in C++ and conducted preliminary experiments over a set of drawings from five well known orthogonal drawing systems. Experimental analysis shows our technique to produce an average 34% improvement in area, 22% in bends, 19% in crossings, and 34% in total edge length.

Item Type:Conference Paper
Additional Information:10.1007/3-540-37623-2_23
Classifications:M Methods > M.999 Others
G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:338

Repository Staff Only: item control page

References

T. Biedl and G. Kant. A Better Heuristic for Orthogonal Graph Drawings. In Proc. 2nd Ann. European Symposium on Algorithms (ESA '94), LNCS, 855, pages 24-35, Springer-Verlag, 1994.

T. Biedl, B. Madden, and I.G. Tollis. The three-phase method: A unified approach to orthogonal graph drawing. In DiBattista, editor. Symposium on Graph Drawing 97, vol. 1353 of LNCS. Springer-Verlag, 1998, pages 391-402.

S. Bridgeman, J. Fanto, A. Garg, R. Tamassia, and L. Vismara. Interactive Giotto: An Algorithm for Interactive Orthogonal Graph Drawing, Proc. GD '97, LNCS 1353, Springer-Verlag, 1997, pages 303-308.

S. Bridgeman, A. Garg, and R. Tamassia. A graph drawing and translation service on the WWW. In S.C. North, editor, Proceedings of Graph Drawing '96 (Proc. GD '96), vol. 1190 of LNCS, Springer-Verlag, 1997, pages 45-52.

R.F. Cohen, G. Di Battista, R. Tamassia, and I.G. Tollis. Dynamic graph drawing: Trees, series-parallel digraphs, and planar st-digraphs. SIAM journal on Computing, 24(5), pp. 970-1001, 1995.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. Theory Appl., 4: 235-282, 1994.

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of four three graph drawing algorithms. Comput. Geom. Theor. Appl., 7:303-326, 1997.

C. Ding and P. Mateti. A Framework for the Automated Drawing of Data Structure Diagrams. IEEE Trans. Softw. Eng., 16(5), 1990, pages 543-557.

J. Doenhardt and T. Lengauer. Algorithmic Aspects of One-Dimensional Layout Compaction. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6(5), 1987, pages 863-879.

C. Esposito. Graph Graphics: Theory and practice. Computers and Mathemetics with Applications, 15(4), 1988, pages 247-253.

S. Even and G. Garnot. Rectilinear Planar Drawings with Few Bends in Each Edge. Tech. Report 797, Comp. Sci. Dept., Technion, Israel Inst. of Tech., 1994.

Jody fanto. Postprocessing of GIOTTO drawings. http://www.cs.brown.edu/people/jrf.

U. Fößmeier. Interactive orthogonal graph drawing: algorithms and bounds. Proc. GD '97, LNCS 1353, Springer-Verlag, 1997, pages 111-123.

U. Fößmeier and M. Kaufmann. Algorithms and area bounds for nonplanar orthogonal drawings. Proc. GD '97, LNCS 1353, Springer-Verlag, 1997, pages 134-145.

M.Y. Hsueh. Symbolic layout and compaction of integrated circuits. Ph. D. Thesis, University of california at Berkeley, 1980.

Goos Kant. Drawing planar graphs using the lmc-ordering. Proc. 33th Ann. IEEE Symp. on Found. Of Comp. Sci., pages 101-110, 1992.

C. Kosak, J. Marks, and S. Shieber. Automating the layout of network diagrams with specified visual organization. IEEE Transactions on Systems, Man and Cybernetics, 24(2):440-454, 1994.

Thomas Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. John Wiley and Sons, 1990.

K. Miriyala, S.W. Hornick, and R. Tamassia. An Incremental Approach to Aesthetic Graph Layout. Proc. Int. Workshop on Computer-Aided Software Engineering (Case '93), 1993, pages 297-308.

K. Misue, P. Eades, W. Lai, and K. Sugiyama. Layout Adjustment and the Mental Map. J. of Visual Languages and Computing, pages 183-210, June 1995.

A. Papakostas. Information visualization: Orthogonal drawings of graphs. Ph. D. thesis, University of Texas at Dallas, 1996.

A. Papakostas, J.M. Six and I.G. Tollis. Experimental and Theoretical Results in Interactive Graph Drawing. In Proc. of the Symp. on Graph Drawing, GD'96, vol. 1190 of LNCS, pages 371-386. Springer Verlag, September 1997.

A. Papakostas and I.G. Tollis. Algorithms for Area-Efficient Orthogonal Drawings. Comput. Geom. Theory Appl., 9:83-110, 1998.

A. Papakostas and I.G. Tollis. Issues in Interactive Orthogonal Graph Drawing. Proc. of GD '95, LNCS, 1027, Springer-Verlag, pages 419-430, 1995. Also available at http://www.utdallas.edu/~tollis/papers.html.

H. Purchase. Which aesthetichas the greatest effect on human understanding? In G. Di Battista, ed., Proc. of the Symp. on Graph Drawing, GD'97, vol. 1353 of LNCS, pages 248-261. Springer Verlag, 1997.

Markus Schäffter. Drawing Graphs on Rectangular Grids. Discr. Appl. Math. 63 (1995), pages 75-89.

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

R. Tamassia, G. Di Battista, and C. Batini. Automatic graph drawing and readability of diagrams. IEEE Transactions on Systems, Man and Cybernetics, SMC-18(1):61-79, 1988.

R. Tamassia and I.G. Tollis. Planar grid embeddings in linear time. IEEE Trans. Circuits Syst., CAS-36(9):1230-1234, 1990.

I.G. Tollis. Graph Drawing and Information Visualization. ACM Computing Surveys, 28A(4), December 1996. Also available at http://www.utdallas.edu/~tollis/SDCR96/TollisGeometry/.