Parallel redrawing
In geometric graph theory, and the theory of structural rigidity, a parallel redrawing of a graph drawing with straight edges in the Euclidean plane or higher-dimensional Euclidean space is another drawing of the same graph such that all edges of the second drawing are parallel to their corresponding edges in the first drawing. A parallel morph of a graph is a continuous family of drawings, all parallel redrawings of each other.
Parallel redrawings include translations, scaling, and other modifications of the drawing that change it more locally. For instance, for graphs drawn as the vertices or edges of a simple polyhedron, a parallel drawing can be obtained by translating the plane of one of the polyhedron's face, and adjusting the positions of the vertices and edges that border that face.[1] A polyhedron is said to be tight if its only parallel redrawings are similarities (combinations of translation and scaling); among the Platonic solids, the cube and dodecahedron are not tight (because of the possibility of translating one face while keeping the others fixed), but the tetrahedron, octahedron, and icosahedron are tight.[2]
In three dimensions, even for drawings where all edges are axis-parallel and the drawing forms the boundary of a polyhedron, there may exist parallel redrawings that cannot be connected by a parallel morph.[3] For two-dimensional planar drawings, with parallel edges required to preserve their orientation, a morph always exists when the slope number is two, but it is NP-hard to determine the existence of a morph for three or more slopes.[4][5] Any parallel morph can be parameterized so that the each point moves with constant speed along a line. The graphs that remain planar throughout such a motion can be derived from pseudotriangulations.[6]
In structural rigidity, the existence of (infinitesimal) parallel redrawings of a structural framework is dual to the existence of an infinitesimal motion, one that preserves its edge lengths but not their orientations. Thus, a framework has one kind of motion if it has the other kind, but detecting the existence of a parallel redrawing may be easier than detecting the existence of an infinitesimal motion.[7]
References
[edit]- ^ Bolker, Ethan; Guillemin, Victor; Holm, Tara (2002), How is a graph like a manifold?, arXiv:math/0206103, Bibcode:2002math......6103B.
- ^ Ward, Thomas (2006), "Mixing and tight polyhedra", Dynamics & stochastics, IMS Lecture Notes Monogr. Ser., vol. 48, Inst. Math. Statist., Beachwood, OH, pp. 169–175, arXiv:math/0503569, doi:10.1214/074921706000000194, MR 2306198, S2CID 16378875.
- ^ Biedl, Therese; Lubiw, Anna; Spriggs, Michael J. (2009), "Morphing polyhedra with parallel faces: counterexamples", Computational Geometry, 42 (5): 395–402, doi:10.1016/j.comgeo.2008.09.006, MR 2512668.
- ^ Biedl, Therese; Lubiw, Anna; Spriggs, Michael J. (2006), "Morphing planar graphs while preserving edge directions", Graph Drawing: 13th International Symposium, GD 2005, Limerick, Ireland, September 12-14, 2005, Revised Papers, Lecture Notes in Computer Science, vol. 3843, Berlin: Springer, pp. 13–24, doi:10.1007/11618058_2, MR 2244496.
- ^ Biedl, Therese; Lubiw, Anna; Petrick, Mark; Spriggs, Michael (2013), "Morphing orthogonal planar graph drawings", ACM Transactions on Algorithms, 9 (4): Art. 29, 24, doi:10.1145/2500118, MR 3119787, S2CID 122564585.
- ^ Streinu, Ileana (2006), "Parallel-redrawing mechanisms, pseudo-triangulations and kinetic planar graphs", Graph Drawing: 13th International Symposium, GD 2005, Limerick, Ireland, September 12-14, 2005, Revised Papers, Lecture Notes in Computer Science, vol. 3843, Berlin: Springer, pp. 421–433, doi:10.1007/11618058_38, MR 2244531.
- ^ Servatius, Brigitte (1993), "Combinatorics and the rigidity of frameworks" (PDF), Newsletter of the SIAM Activity Group on Discrete Mathematics.