Home | Issues | About JGAA | Instructions for Authors |
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.
Reviewed: October 2010.
Revised: October 2010.
Accepted: December 2010.
Final: February 2011.
Published: February 2011.
Communicated by
Stephen G. Kobourov
|
Journal Supporters
|