Article

Graphs, They Are Changing

Authors:

Carsten GörgAuthors Info & Claims

GD '02: Revised Papers from the 10th International Symposium on Graph Drawing

Pages 23 - 30

Published: 26 August 2002 Publication History

Abstract

In this paper we present a generic algorithm for drawing sequences of graphs. This algorithm works for different layout algorithms and related metrics and adjustment strategies. It differs from previous work on dynamic graph drawing in that it considers all graphs in the sequence (offline) instead of just the previous ones (online) when computing the layout for each graph of the sequence. We introduce several general adjustment strategies and give examples of these strategies in the context of force-directed graph layout. Finally some results from our first prototype implementation are discussed.

References

[1]

U. Brandes and D. Wagner. A Bayesian paradigm for dynamic graph layout. In Graph Drawing (Proc. GD '97) , volume 1353 of Lecture Notes Computer Science . Springer-Verlag, 1997.

[2]

Ulrik Brandes. Drawing on physical analogies. In Drawing Graphs {11} . 2001.

[3]

Jürgen Branke. Dynamic graph drawing. In Drawing Graphs {11} . 2001.

[4]

S. Bridgeman and R. Tamassia. Difference metrics for interactive orthogonal graph drawing algorithms. In Proceedings of 6th International Symposium on Graph Drawing GD'98 . Springer LNCS 1457, 1998.

[5]

R.F. Cohen, G. Di Battista, R. Tamassia, and I.G. Tollis. Dynamic graph drawings: Trees, series-parallel digraphs, and st -digraphs. SIAM Journal on Computing , 24(5), 1995.

[6]

S. Diehl, C. Görg, and A. Kerren. Foresighted Graphlayout. Technical Report A/02/2000, FR 6.2 - Informatik, University of Saarland, December 2000. http://www.cs.uni-sb.de/tr/FB14.

[7]

Stephan Diehl, Carsten Görg, and Andreas Kerren. Preserving the Mental Map using Foresighted Layout. In Proceedings of Joint Eurographics - IEEE TCVG Symposium on Visualization VisSym'01 . Springer Verlag, 2001.

[8]

P. Eades. A heuristic for graph drawing. Congressus Numerantium , 42, 1984.

[9]

C. Friedrich and M. E. Houle. Graph Drawing in Motion II. In Proceedings of Graph Drawing 2001 . Springer LNCS (to appear), 2001.

[10]

M. R. Garey and D. S. Johnson. Computers and Intractability. A Guide to the Theory of NP-Completeness . Freeman and Company, 1979.

[11]

M. Kaufmann and D. Wagner, editors. Drawing Graphs - Methods and Models , volume 2025 of Lecture Notes in Computer Science . Springer-Verlag, 2001.

[12]

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

[13]

K. Misue, P. Eades, W. Lai, and K. Sugiyama. Layout Adjustment and the Mental Map. Journal of Visual Languages and Computing , 6(2):183-210, 1995.

[14]

A. Papakostas and I.G. Tollis. Interactive orthogonal graph drawing. IEEE Transactions on Computers , 47(11), 1998.

[15]

H.C. Purchase, R.F. Cohen, and M. James. Validating graph drawing aesthetics. In F. J. Brandenburg, editor, Graph Drawing (Proc. GD '95) , volume 1027 of Lecture Notes Computer Science . Springer-Verlag, 1996.

[16]

G. Sander. Visualization Techniques for Compiler Construction . Dissertation (in german), University of Saarland, Saarbrücken (Germany), 1996.

Cited By

Abdelaal MHlawatsch MBurch MWeiskopf DWeiskopf DBeck FDachsbacher CSadlo F(2018)Clustering for stacked edge splattingProceedings of the Conference on Vision, Modeling, and Visualization10.2312/vmv.20181262(127-134)Online publication date: 10-Oct-2018
https://dl.acm.org/doi/10.2312/vmv.20181262
Zoubek FLanger PMayerhofer TWąsowski APaige RHaugen Ø(2018)Visualizations of Evolving Graphical Models in the Context of Model ReviewProceedings of the 21th ACM/IEEE International Conference on Model Driven Engineering Languages and Systems10.1145/3239372.3239403(381-391)Online publication date: 14-Oct-2018
https://dl.acm.org/doi/10.1145/3239372.3239403
Burch MKerren AKlein KLi Y(2018)Property-Driven Dynamic Call Graph ExplorationProceedings of the 11th International Symposium on Visual Information Communication and Interaction10.1145/3231622.3231630(72-79)Online publication date: 13-Aug-2018
https://dl.acm.org/doi/10.1145/3231622.3231630
Show More Cited By

Index Terms

Graphs, They Are Changing
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Total domination changing and stable graphs upon vertex removal

A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. A graph is total domination vertex removal ...
Collapsible graphs and Hamiltonian connectedness of line graphs

Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai [Z.-H. Chen, H.-J. Lai, Reduction techniques for super-Eulerian graphs and related topics-an update, in: Ku Tung-Hsin (Ed.), Combinatorics and Graph Theory, vol. 95, ...
Comparability Graphs Among Cover-Incomparability Graphs
Algorithms and Discrete Applied Mathematics
Abstract
Comparability graphs and cover-incomparability graphs (C-I graphs) are two interesting classes of graphs from posets. Comparability graph of a poset $P = (V, \leq)$ is a graph with vertex set V and two vertices u and v are adjacent in V if u and v are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

GD '02: Revised Papers from the 10th International Symposium on Graph Drawing

August 2002

386 pages

ISBN:3540001581

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 26 August 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
1
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Abdelaal MHlawatsch MBurch MWeiskopf DWeiskopf DBeck FDachsbacher CSadlo F(2018)Clustering for stacked edge splattingProceedings of the Conference on Vision, Modeling, and Visualization10.2312/vmv.20181262(127-134)Online publication date: 10-Oct-2018
https://dl.acm.org/doi/10.2312/vmv.20181262
Zoubek FLanger PMayerhofer TWąsowski APaige RHaugen Ø(2018)Visualizations of Evolving Graphical Models in the Context of Model ReviewProceedings of the 21th ACM/IEEE International Conference on Model Driven Engineering Languages and Systems10.1145/3239372.3239403(381-391)Online publication date: 14-Oct-2018
https://dl.acm.org/doi/10.1145/3239372.3239403
Burch MKerren AKlein KLi Y(2018)Property-Driven Dynamic Call Graph ExplorationProceedings of the 11th International Symposium on Visual Information Communication and Interaction10.1145/3231622.3231630(72-79)Online publication date: 13-Aug-2018
https://dl.acm.org/doi/10.1145/3231622.3231630
(2018)Tabu search for the dynamic Bipartite Drawing ProblemComputers and Operations Research10.1016/j.cor.2017.10.01191:C(1-12)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1016/j.cor.2017.10.011
Burch MHlawatsch MWeiskopf D(2017)Visualizing a Sequence of a Thousand Graphs or Even MoreComputer Graphics Forum10.1111/cgf.1318536:3(261-271)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1111/cgf.13185
Beck FBurch MDiehl SWeiskopf D(2017)A Taxonomy and Survey of Dynamic Graph VisualizationComputer Graphics Forum10.1111/cgf.1279136:1(133-159)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1111/cgf.12791
Burch MZhang KKerren A(2016)The Dynamic Call Graph MatrixProceedings of the 9th International Symposium on Visual Information Communication and Interaction10.1145/2968220.2968226(1-8)Online publication date: 24-Sep-2016
https://dl.acm.org/doi/10.1145/2968220.2968226
Cortés XSerratosa F(2016)Cooperative pose estimation of a fleet of robots based on interactive points alignmentExpert Systems with Applications: An International Journal10.1016/j.eswa.2015.09.04945:C(150-160)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1016/j.eswa.2015.09.049
Gruenhage GOpper MBarthelme S(2016)Visualizing the effects of a changing distance on data using continuous embeddingsComputational Statistics & Data Analysis10.1016/j.csda.2016.06.006104:C(51-65)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1016/j.csda.2016.06.006
Arenas MBotoeva ECalvanese DRyzhikov V(2016)Knowledge base exchangeArtificial Intelligence10.1016/j.artint.2016.05.002238:C(11-62)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.artint.2016.05.002
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents