Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00223 Morphing Planar Graph Drawings with Bent Edges Anna Lubiw and Mark Petrick Vol. 15, no. 2, pp. 205-227, 2011. Regular paper Abstract We give an algorithm to morph between two planar drawings of a graph, preserving planarity, but allowing edges to bend during the course of the morph. The morph is polynomial size and discrete: it uses a polynomial number of elementary steps, where each elementary step is a linear morph that moves each vertex along a straight line at uniform speed. Although there are previously-known planarity-preserving morphs that do not require edge bends, it is an open problem to find polynomial-size discrete morphs. We achieve polynomial size at the expense of edge bends.
|
Submitted: May 2010. Accepted: December 2010. Reviewed: October 2010. Revised: October 2010. Final: February 2011. Published: February 2011. Communicated by Stephen Kobourov |
Journal of Graph Algorithms and Applications |