Abstract
Constrained graph layout is a recent generalisation of force-directed graph layout which allows constraints on node placement. We give a constrained graph layout algorithm that takes an initial feasible layout and improves it while preserving the topology of the initial layout. The algorithm supports poly-line connectors and clusters. During layout the connectors and cluster boundaries act like impervious rubber-bands which try to shrink in length. The intended application for our algorithm is dynamic graph layout, but it can also be used to improve layouts generated by other graph layout techniques.
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
Bertault, F.: A force-directed algorithm that preserves edge crossing properties. In: Kratochvíl, J. (ed.) GD 1999. LNCS, vol. 1731, pp. 351–358. Springer, Heidelberg (1999)
Bridgeman, S.S., Fanto, J., Garg, A., Tamassia, R., Vismara, L.: InteractiveGiotto: An algorithm for interactive orthogonal graph drawing. In: DiBattista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 303–308. Springer, Heidelberg (1997)
Dwyer, T., Koren, Y., Marriott, K.: Drawing directed graphs using quadratic programming. IEEE Transactions on Visualization and Computer Graphics 12(4), 536–548 (2006)
Dwyer, T., Koren, Y., Marriott, K.: IPSep-CoLa: An incremental procedure for separation constraint layout of graphs. IEEE Transactions on Visualization and Computer Graphics 12(5), 821–828 (2006)
Dwyer, T., Marriott, K., Wybrow, M.: Dunnart: A constraint-based network diagram authoring tool. In: GD 2008. LNCS, vol. 5417. Springer, Heidelberg (to appear, 2009)
Dwyer, T., Marriott, K., Wybrow, M.: Exploration of networks using overview+detail with constraint-based cooperative layout. IEEE Transactions on Visualization and Computer Graphics (InfoVis 2008) (to appear 2008)
Dwyer, T., Marriott, K., Wybrow, M.: Integrating edge routing into force-directed layout. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 8–19. Springer, Heidelberg (2007)
Eiglsperger, M., Fekete, S.P., Klau, G.W.: Drawing Graphs: Methods and Models, chap. Orthogonal graph drawing, pp. 121–171. Springer, London (2001)
Frishman, Y., Tal, A.: Online dynamic graph drawing. In: Eurographics/IEEE-VGTC Symp. on Visualization. Eurographics Association (2007)
Gansner, E., Koren, Y., North, S.: Graph drawing by stress majorization. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 239–250. Springer, Heidelberg (2005)
Gutwenger, C., Mutzel, P., Weiskircher, R.: Inserting an edge into a planar graph. In: SODA 2001: Proc. of the 12th Annual ACM-SIAM Symp. on Discrete Algorithms, pp. 246–255. Society for Industrial and Applied Mathematics (2001)
He, W., Marriott, K.: Constrained graph layout. Constraints 3, 289–314 (1998)
Kamada, T., Kawai, S.: An algorithm for drawing general undirected graphs. Information Processing Letters 31, 7–15 (1989)
Misue, K., Eades, P., Lai, W., Sugiyama, K.: Layout adjustment and the mental map. Journal of Visual Languages and Computing 6(2), 183–210 (1995)
North, S.C., Woodhull, G.: Online hierarchical graph drawing. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 232–246. Springer, Heidelberg (2002)
Wybrow, M., Marriott, K., Stuckey, P.J.: Incremental connector routing. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 446–457. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dwyer, T., Marriott, K., Wybrow, M. (2009). Topology Preserving Constrained Graph Layout. In: Tollis, I.G., Patrignani, M. (eds) Graph Drawing. GD 2008. Lecture Notes in Computer Science, vol 5417. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00219-9_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-00219-9_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00218-2
Online ISBN: 978-3-642-00219-9
eBook Packages: Computer ScienceComputer Science (R0)