Morphing Planar Graph Drawings Efficiently

DOI10.1007/978-3-319-03841-4_5MaRDI QIDQ2867642zbMATH OpenOpenAlexFDO

Authors Patrizio Angelini, Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli

Publication date 20 December 2013

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.4291

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: A morph between two straight-line planar drawings of the same graph is a continuous transformation from the first to the second drawing such that planarity is preserved at all times. Each step of the morph moves each vertex at constant speed along a straight line. Although the existence of a morph between any two drawings was established several decades ago, only recently it has been proved that a polynomial number of steps suffices to morph any two planar straight-line drawings. Namely, at SODA 2013, Alamdari et al.[1] proved that any two planar straight-line drawings of a planar graph can be morphed in O(n^4) steps, while O(n^2) steps suffice if we restrict to maximal planar graphs. In this paper, we improve upon such results, by showing an algorithm to morph any two planar straight-line drawings of a planar graph in O(n^2) steps; further, we show that a morph with O(n) steps exists between any two planar straight-line drawings of a series-parallel graph.

Recommendations

• Morphing Planar Graph Drawings Optimally
• Morphing orthogonal planar graph drawings
• Morphing planar graph drawings with a polynomial number of steps
• How to morph planar graph drawings
• Morphing planar graph drawings with bent edges
• Morphing planar graph drawings with bent edges
• Graph Drawing
• Convex Drawings of Hierarchical Graphs in Linear Time, with Applications to Planar Graph Morphing

Cited in

(31)

• Pole dancing: 3D morphs for tree drawings
• Planar and toroidal morphs made easier
• Optimal morphs of planar orthogonal drawings. II
• Graph drawing with morphing partial edges
• Planar polyline drawings via graph transformations
• Morphing planar graph drawings with bent edges
• Morphing Planar Graphs in Spherical Space
• Topological morphing of planar graphs
• AN OPTIMAL MORPHING BETWEEN POLYLINES
• Morphing Contact Representations of Graphs
• Computing optimal homotopies over a spiked plane with polygonal boundary
• Optimal morphs of planar orthogonal drawings
• Morphing Planar Graph Drawings Optimally
• Pole dancing: 3D morphs for tree drawings
• Morphing planar graph drawings with bent edges
• Morphing Planar Graphs in Spherical Space
• How to morph planar graph drawings
• Morphing planar graph drawings with a polynomial number of steps
• Planar and Toroidal Morphs Made Easier
• Morphing orthogonal planar graph drawings
• Graph Drawing
• Graph Drawing
• Convexity-increasing morphs of planar graphs
• Upward planar morphs
• Upward planar morphs
• How to morph a tree on a small grid
• How to morph a tree on a small grid
• Morphing triangle contact representations of triangulations
• Morphing tree drawings in a small 3D grid
• Shape-faithful graph drawings
• How to morph graphs on the torus

This page was built for publication: Morphing Planar Graph Drawings Efficiently

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2867642)