Loading...
Morphing Triangle Contact Representations of Triangulations
Angelini, Patrizio
Chaplick, Steven Cornelsen, Sabine Da Lozzo, Giordano Roselli, Vincenzo
Chaplick, Steven
Cornelsen, Sabine
Da Lozzo, Giordano
Roselli, Vincenzo
Citations
Altmetric:
Abstract
A 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.
Description
Date
2023
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Nature
Research Projects
Organizational Units
Journal Issue
Keywords
Planar graphs, Graph drawing, Morphing, Contact representation
Citation
Angelini, 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.