Angelini, PatrizioChaplick, StevenCornelsen, SabineDa Lozzo, GiordanoRoselli, Vincenzo2024-09-252024-09-252023Angelini, Patrizio, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo, and Vincenzo Roselli. “Morphing Triangle Contact Representations of Triangulations.” Discrete & Computational Geometry 70 (3): 991–1024. 2023.https://doi.org/10.1007/s00454-022-00475-9https://hdl.handle.net/20.500.14490/328A morph is a continuous transformation between two representations of a graph. We consider the problem of morphing between contact representations of a plane graph. In an F-contact representation of a plane graph G, vertices are realized by internally disjoint elements from a family F of connected geometric objects. Two such elements touch if and only if their corresponding vertices are adjacent. These touchings also induce the same embedding as in G. In a morph between two F-contact representations we insist that at each time step (continuously throughout the morph) we have an Fcontact representation. We focus on the case when F is the family of triangles in R2 that are the lower-right half of axis-parallel rectangles. Such RT-representations exist for every plane graph and right triangles are one of the simplest families of shapes supporting this property. Moreover, they naturally correspond to 3-orientations. Thus, they provide a natural case to study regarding morphs of contact representations of plane graphs. We characterize the pairs of RT-representations admitting a morph between each other via the respective 3-orientations. Our characterization leads to a polynomial-time algorithm to decide whether there is a morph between two RTrepresentations of an n-vertex plane triangulation, and, if so, computes a morph with O(n2) steps. Each of these steps is a linear morph moving the endpoints of each triangle at constant speed along straight-line trajectories. Our characterization also implies that for 4-connected plane triangulations there is a morph between every pair of RT-representations where the “top-most” triangle in both representations corresponds to the same vertex.enAttribution 4.0 Internationalhttp://creativecommons.org/licenses/by/4.0/Planar graphsGraph drawingMorphingContact representationArticle