Intersection-Free Morphing of Planar Graphs

Cesim Erten1, Stephen G. Kobourov1, Chandan Pitta2

Morphing refers to the process of transforming one shape (the source) into another (the target). Morphing is widely used in computer graphics, animation, and modeling. In planar graph morphing we would like to transform a given source graph to another pre-specified target graph. A smooth transformation of one graph into another can be useful for numerous problems from graph drawing. In particular, when dealing with dynamic graphs and graphs that change through time, it is crucial to preserve the mental map of the user. Thus, it is important to minimize the changes to the drawing and to create a smooth transition between consecutive drawings. Another important goal is to avoid creating any intersections throughout the morph. We designed and implemented an algorithm that can morph between drawings with straight-line segments, bends and it relies on a combination of techniques to achieve smooth transformations: rigid morphing, compatible triangulations, as well as morphing based on interpolation of the convex representations of the graphs.

For example given the two layouts on the left(top-left is the source, bottom-right drawn opaquely is the target layout) we are interested in finding a smooth sequence of layouts starting from the source ending with the target layout. We want each intermediate layout in the sequence contain no edge-crossings. Our algorithm has 4 main parts:
  • Apply Rigid motion on source layout
  • Introduce necessary bends
  • Compatibly triangulate the two layouts
  • Morph using convex representations

Paper, Implementation, Movie Gallery

1 Dept. of Computer Science
University of Arizona
2 Dept. of Electrical and Comp. Eng.
University of Arizona