Morphing Planar Graph Drawings with Bent Edges |
| |
| Institution: | 1. David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada, N2L 3G1;1. École Normale Supérieure, Paris, France;2. Rudjer Bos˘ković Institute, Bijenic˘ka 54, 10000 Zagreb, Croatia;1. School of Computer Science, Carleton University, Ottawa, ON, Canada;2. School of Computer Science, University of Waterloo, Waterloo, ON, Canada |
| |
| Abstract: | We give an algorithm to morph between two planar drawings of a graph, preserving planarity, but allowing edges to bend. The morph uses a polynomial number of elementary steps, where each elementary step is a linear morph that moves each vertex in a straight line at uniform speed. Although there are planarity-preserving morphs that do not require edge bends, it is an open problem to find polynomial-size morphs. We achieve polynomial size at the expense of edge bends. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
