Experimental and Theoretical Results in Interactive Orthogonal Graph Drawing

Papakostas, Achilleas and Six, Janet M. and Tollis, Ioannis G. (1997) Experimental and Theoretical Results in Interactive Orthogonal Graph Drawing. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996, Berkeley, California, USA , pp. 371-386 (Official URL: http://dx.doi.org/10.1007/3-540-62495-3_61).

Full text not available from this repository.

Abstract

Interactive Graph Drawing allows the user to dynamically interact with a drawing as the design progresses while preserving the user's mental map. This paper presents a theoretical analysis of Relative-Coordinates and an extensive experimental study comparing the performance of two interactive orthogonal graph drawing scenaria: No-Change, and Relative-Coordinates. Our theoretical analysis found that the Relative-Coordinates scenario builds a drawing that has no more than 3n-1 bends, while the area of the drawing is never larger than 2.25n². Also, no edge has more than 3 bends at any time during the drawing process. To conduct the expirements, we used a large set of test data consisting of 11,491 graphs (ranking from 6 to 100 nodes) and compared the behavior of the above two scenaria with respect to various aesthetic properties (e.g., area, bends, crossings, edge length, etc.) of the corresponding drawings. The Relative-Coordinates scenario was a winner over No-change under any aesthetic measure considered in our experiments. Moreover, the practical behavior of the two scenaria was considerably better than the established theoretical bounds, in most cases.

Item Type:Conference Paper
Additional Information:10.1007/3-540-62495-3_61
Classifications:M Methods > M.300 Dynamic / Incremental / Online
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:110

Repository Staff Only: item control page

References

Therese Biedl. Embedding Nonplanar Graphs in the Rectangular Grid. Rutcor Research Report 27-93, 1993.

T. Biedl and G. Kant. A Better Heuristic for Orthogonal Graph Drawings. Technical Report, Utrecht Univ., Dept. of Comp. Sci., UU-CS-1995-04. Prelim. version appeared in Proc. 2nd Ann. European Symposium on Algorithms (ESA '94), LNCS, 855, pages 24-35, Springer-Verlag, 1994.

R. Cohen, G. Di Battista, R. Tamassia, and I.G. Tollis. Dynamic Graph Drawings: Trees, Series-Parallel Digraphs, and Planar st-Digraphs. SIAM Journal on Computing, vol. 24, no 5, pages 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., vol. 4, no 5, 1994, pp. 235-282. Also available via anonymous ftp from ftp.cs.brown.edu, gdbiblio.tex.Z and gdbiblio.ps.Z in /pub/papers/compgeo.

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of three graph drawing algorithms. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 306-315, 1995. The version of the paper with the four algorithms can be obtained from http://www.cs.brown/people/rt.

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.

S. Even and R.E. Tarjan. Computing an st-numbering. Theoretical Computer Science, 2:339-344, 1976.

M. Himsolt. Comparing and evaluating layout algorithms within GraphEd. J. Visual Lang. Comput., 6(3), pages 255-273, 1995.

M. Himsolt. GraphEd: a graphical platform for the implementation of graph algorithms. Proc. DIMACS Workshop GD '94, LNCS, 894, Springer-Verlag, pages 182-193, 1994.

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

F.T. Leighton. New lower bound techniques for VLSI. Proc. 22nd Ann. IEEE Symp. on Found. Of Comp. Sci., pages 1-12, 1981.

C.E. Leiserson. Area-Efficient Graph Layouts (for VLSI). Proc. 21st Ann. IEEE Symp. on Found. Of Comp. Sci., pages 270-281, 1980.

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.

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 and I.G. Tollis. Algorithms for Area-Efficient Orthogonal Drawings. Tech. Report UTDCS-06-95, The University of Texas at Dallas, 1995. Also available on the WWW at http://wwwpub.utdallas.edu/~tollis.

A. Papakostas and I.G. Tollis. Improved Algorithms and Bounds for Orthogonal Drawings. Proc. DIMACS Workshop GD '94, LNCS, 894, Springer-Verlag, pages 40-51, 1994.

A. Papakostas and I.G. Tollis. Issues in Interactive Orthogonal Graph Drawing. Proc. of GD '95, LNCS, 1027, Springer-Verlag, pages 419-430, 1995.

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

J. Storer. On minimal node-cost planar embeddings. Network 14 (1984), pages 181-212.

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 and I.G. Tollis. Planar grid embeddings in linear time. IEEE Trans. Circuits Syst., CAS-36(9):1230-1234, 1989.

Tom Sawyer Software Corp. GLT development group. Graph Layout Toolkit User's Guide. Berkeley, California, 1995.

Tom Sawyer Software Corp. GLT development group. Graph Layout Toolkit Reference Manual. Berkeley, California, 1995.

L. Valiant. University Considerations in VLSI Circuits", IEEE Trans. on Comp., vol. C-30, no 2, (1981), pages 135-140.