Topology Preserving Constrained Graph Layout

Topology Preserving Constrained Graph Layout Tim Dwyer, Kim Marriott, and Michael Wybrow Clayton School of Information Technology, Monash University, Clayton, Victoria 3800, Australia, Tim.Dwyer,Kim.Marriott,Michael.Wybrow @infotech.monash.edu.au { } 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. 1 Introduction A core requirement of dynamic graph layout is stability of layout during changes to the graph so as to preserve the user’s mental model of the graph. One natural requirement to achieve this is to preserve the topology of the current layout during layout changes. While topology preservation has been used for dynamic layout based on orthogonal graph layout, its use in force-directed approaches to dynamic layout is much less common. Constrained graph layout [12, 3, 4] is a recent generalisation of the force- directed model for graph layout. Like force-directed methods, these techniques find a layout minimising a goal function such as the standard stress goal function which tries to place all pairs of nodes their ideal (graph-theoretic) distance apart. However, unlike force directed methods, constrained graph layout algorithms al- low the goal to be minimised subject to placement constraints on the nodes. In this paper we detail a constrained graph layout algorithm that preserves the topology of the initial layout. The primary motivation for our development of this algorithm was to support dynamic layout but it can also be used to im- prove layouts generated by other graph layout techniques such as planarisation techniques [11]. Our algorithm supports network diagrams with poly-line connectors and arbi- trary node clusters. It ensures that the nodes do not overlap and that additional constraints on the layout—such as alignment and downward pointing edges— remain satisfied. During layout optimisation the paths, i.e poly-line connectors and cluster boundaries, act like rubber-bands, trying to shrink in length and hence, in the case of connectors, straighten. Like physical rubber bands, the paths are impervious and do not allow nodes and other paths to pass through them. Thus, the initial layout topology is preserved. Figure 1 shows (a) Euler diagram example layouts obtained with our al- sucrose phosphate sucrose phosphatase 6-phosphate P fructose gorithm. 6-phosphate sucrose phosphate sucrose synthase UDP Extending constrained graph lay- sucrose synthase invertase UDP - glucose fructose out to handle topology preservation ATP fructokinase UTP glucose UDP glucose is conceptually quite natural since ADP pyrophosphorylase fructose PP 6-phosphate ATP topology preservation can be regarded hexokinase phosphoglucose isomerase glucose 1-phosphate glucose as a...

Website: www.csse.monash.edu.au | Filesize: -
No of Page(s): 12
Download Topology Preserving Constrained Graph Layout - Clayton - Monash ....pdf