### Abstract

In 1944, Cairns proved the following theorem: given any two straight-line planar drawings of a triangulation with the same outer face, there exists a morph (i.e., a continuous transformation) between the two drawings so that the drawing remains straight-line planar at all times. Cairns's original proof required exponentially many morphing steps. We prove that there is a morph that consists of O(n^{2}) steps, where each step is a linear morph that moves each vertex at constant speed along a straight line. Using a known result on compatible triangulations this implies that for a general planar graph G and any two straight-line planar drawings of G with the same embedding, there is a morph between the two drawings that preserves straight-line planarity and consists of O(n^{4}) steps.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 |

Publisher | Association for Computing Machinery |

Pages | 1656-1667 |

Number of pages | 12 |

ISBN (Print) | 9781611972511 |

DOIs | |

State | Published - Jan 1 2013 |

Externally published | Yes |

Event | 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 - New Orleans, LA, United States Duration: Jan 6 2013 → Jan 8 2013 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 |
---|---|

Country | United States |

City | New Orleans, LA |

Period | 1/6/13 → 1/8/13 |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Morphing planar graph drawings with a polynomial number of steps'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013*(pp. 1656-1667). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973105.119