Morphing Planar Graphs While Preserving Edge Directions

Biedl, Therese and Lubiw, Anna and Spriggs, Michael (2006) Morphing Planar Graphs While Preserving Edge Directions. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005 , pp. 13-24(Official URL:

Full text not available from this repository.


Two straight-line drawings P,Q of a graph (V,E) are called parallel if, for every edge (u,v) in E, the vector from u to v has the same direction in both P and Q. We study problems of the form: given simple, parallel drawings P,Q does there exist a continuous transformation between them such that intermediate drawings of the transformation remain simple and parallel with P (and Q)? We prove that a transformation can always be found in the case of orthogonal drawings; however, when edges are allowed to be in one of three or more slopes the problem becomes NP-hard.

Item Type: Conference Paper
Additional Information: 10.1007/11618058_2
Classifications: P Styles > P.600 Poly-line
P Styles > P.540 Planar

Actions (login required)

View Item View Item