How to morph planar graph drawings
From MaRDI portal
Abstract: Given an -vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous transformation) between the two drawings that preserves straight-line planarity and consists of steps, which we prove is optimal in the worst case. Each step is a unidirectional linear morph, which means that every vertex moves at constant speed along a straight line, and the lines are parallel although the vertex speeds may differ. Thus we provide an efficient version of Cairns' 1944 proof of the existence of straight-line planarity-preserving morphs for triangulated graphs, which required an exponential number of steps.
Recommendations
Cites work
- Convex drawings of hierarchical planar graphs and clustered planar graphs
- Deformations of plane graphs
- Deformations of Plane Rectilinear Complexes
- Geometric folding algorithms. Linkages, origami, polyhedra
- Graph Drawing
- Graph Drawing in Motion
- How to Draw a Graph
- How to morph tilings injectively
- scientific article; zbMATH DE number 3882450 (Why is no real title available?)
- scientific article; zbMATH DE number 3885930 (Why is no real title available?)
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- scientific article; zbMATH DE number 1433426 (Why is no real title available?)
- INTRINSIC MORPHING OF COMPATIBLE TRIANGULATIONS
- Morphing orthogonal planar graph drawings
- Morphing orthogonal planar graph drawings
- Morphing Planar Graph Drawings Efficiently
- Morphing Planar Graph Drawings Optimally
- Morphing planar graph drawings with a polynomial number of steps
- Morphing planar graph drawings with bent edges
- Morphing Planar Graphs in Spherical Space
- Morphing simple polygons
- On compatible triangulations of simple polygons
- Optimal morphs of convex drawings
- Piecewise-Linear Interpolation between Polygonal Slices
- Straightening polygonal arcs and convexifying polygonal cycles
- Warp-guided object-space morphing
Cited in
(41)- Pole dancing: 3D morphs for tree drawings
- Planar and toroidal morphs made easier
- Morphing tree drawings in a small 3D grid
- On compatible triangulations with a minimum number of Steiner points
- Optimal morphs of planar orthogonal drawings. II
- Minimal representations of order types by geometric graphs
- Graph drawing with morphing partial edges
- On compatible matchings
- Introduction to reconfiguration
- On morphing 1-planar drawings
- Morphing Planar Graph Drawings Efficiently
- Height-preserving transformations of planar graph drawings
- Morphing planar graph drawings with bent edges
- Morphing Planar Graphs in Spherical Space
- Topological morphing of planar graphs
- On Compatible Matchings
- Morphing Contact Representations of Graphs
- Optimal morphs of planar orthogonal drawings
- Minimal Representations of Order Types by Geometric Graphs
- 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
- Optimal morphs of convex drawings
- Morphing planar graph drawings with a polynomial number of steps
- Planar and Toroidal Morphs Made Easier
- Morphing orthogonal planar graph drawings
- Convexity-increasing morphs of planar graphs
- Upward planar morphs
- Upward planar morphs
- How to morph a tree on a small grid
- Convexity-increasing morphs of planar graphs
- Morphing triangle contact representations of triangulations
- Morphing tree drawings in a small 3D grid
- Morphing rectangular duals
- How to morph graphs on the torus
- Morphing graph drawings in the presence of point obstacles
- Morphing planar graph drawings via orthogonal box drawings
- Flips in odd matchings
- From Tutte to Floater and Gotsman: on the resolution of planar straight-line drawings and morphs
- Shelling and sinking graphs on the sphere
This page was built for publication: How to morph planar graph drawings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5737811)
