Topology Preserving Constrained Graph Layout

Dwyer, Tim and Marriott, Kim and Wybrow, Michael (2009) Topology Preserving Constrained Graph Layout. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 230-241 (Official URL:

Full text not available from this repository.


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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_22
Classifications:M Methods > M.400 Force-directed / Energy-based
M Methods > M.300 Dynamic / Incremental / Online
ID Code:909

Repository Staff Only: item control page


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: 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, UK (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 ’01: 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)