Difference Metrics for Interactive Orthogonal Graph Drawing Algorithms

Bridgeman, Stina and Tamassia, Roberto (1998) Difference Metrics for Interactive Orthogonal Graph Drawing Algorithms. In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 57-71 (Official URL: http://dx.doi.org/10.1007/3-540-37623-2_5).

Full text not available from this repository.


Preserving the “mental map” is major goal of interactive graph drawing algorithms. Several models have been proposed for formalizing the notion of mental map. Additional work needs to be done to formulate and validate “difference” metrics which can be used in practice. This paper introduces a framework for defining and validating metrics to measure the difference between two drawings of the same graph.

Item Type:Conference Paper
Additional Information:10.1007/3-540-37623-2_5
Classifications:M Methods > M.999 Others
M Methods > M.300 Dynamic / Incremental / Online
G Algorithms and Complexity > G.999 Others
P Styles > P.600 Poly-line > P.600.700 Orthogonal
G Algorithms and Complexity > G.560 Geometry
ID Code:243

Repository Staff Only: item control page


H. Alt, O. Aichholzer, and G. Rote. Matching shapes with a reference point. Internat. J. Comput. Geom. Appl., 1997. to appear.

T. Biedl and M. Kaufmann. Area-efficient static and incremental graph drawings. In 5th European Symposium on Algorithms, vol. 1284 of LNCS, pages 37-52. Springer-Verlag, 1997.

U. Brandes and D. Wagner. A Bayesian paradigm for dynamic graph layout. Proc. of Graph Drawing '97. Springer, LNCS, vol. 1353, pages 236-247, 1997.

S.S. Bridgeman, J. Fanto, A. Garg, R. Tamassia, and L. Vismara. Interactive-Giotto: An algorithm for interactive orthogonal graph drawing. Proc. of Graph Drawing '97. Springer, LNCS, vol. 1353, pages 303-308, 1997.

L.P. Chew, M.T. Goodrich, D.P. Huttenlocher, K. Kedem, J.M. Kleinberg, and D. Kravets. Geometric pattern matching under euclidian motion. Comp. Geom. Theor. Appl., 7:113-124, 1997.

R.F. Cohen, G. Di Battista, R. Tamassia, and I.G. Tollis. Dynamic graph drawings: Trees, series-parallel digraphs, and planar ST-digraphs. SIAM J. Comput., 24(5):970-1001, 1995.

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

P. Eades, W. Lai, K. Misue, and K. Sugiyama. Preserving the Mental Map of a Diagram. In Proc. Compugraphics `91, pages 24-33, 1991.

U. Fößmeier. Interactive orthogonal graph drawing: Algorithms and bounds. Proc. of Graph Drawing '97. Springer, LNCS, vol. 1353, pages 111-123, 1997.

J.E. Goodman and R. Pollack. Multidimensional sorting. SIAM J. Comput., 12:484-507, 1983.

M.T. Goodrich, J.S.B. Mitchell, and M.W. Orletsky. Practical methods for approximate geometric pattern matching und derrigid motion. IEEE Trans. Pattern Anal. Mach. Intell, to appear.

K. Imai, S. Sumino, and H. Imai. Minimax geometric fitting of two corresponding sets of points. In Proc. 5th Annu. Symposium Comput. Geom., pages 266-275, 1989.

K.A. Lyons, H. Meijer, and D. Rappaport. Algorithms for cluster busting in anchored graph drawing. Journal of Graph Algorithms and Applications, 2(1):1-24, 1998.

K. Miriyala, S.W. Hornick, and R. Tamassia. An incremental approach to aesthetic graph layout. In Proc. Internat. Workshop on Computer-Aided Software Engineering, 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.

S. Moen. Drawing dynamic trees. IEEE Software, 7:21-8, 1990.

S. North. Incremental layout in DynaDAG. Proc. of Graph Drawing '95. Springer, LNCS, vol. 1027, pages 409-418, 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. Interactive orthogonal graph drawing. Proc. of the Symp. on Graph Drawing, GD'95, vol. 1027 of LNCS. Springer Verlag, 1996.

H. Purchase. Which aesthetic has the greatest effect on human understanding? Proc. of the Symp. on Graph Drawing, GD'97, vol. 1353 of LNCS, pages 248-261. Springer Verlag, 1997.

H. Purchase, R.F. Cohen, and M. James. Validating graph drawing aesthetics. Proc. of the Symp. on Graph Drawing, GD'95, vol. 1027 of LNCS, pages 435-446. Springer Verlag, 1996.

K. Ryall, J. Marks, and S. Shieber. An Interactive System for Drawing Graphs. Proc. of the Symp. on Graph Drawing, GD'96, vol. 1190 of LNCS, pages 387-393. Springer Verlag, 1997.

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.