Parallel-Redrawing Mechanisms, Pseudo-Triangulations and Kinetic Planar Graphs

摘要: We study parallel redrawing graphs: graphs embedded on moving point sets in such a way that edges maintain their slopes all throughout the motion. The configuration space of graph is an oriented-projective nature, and its combinatorial structure relates to rigidity theoretic parameters graph. For appropriate parametrization points move with constant speeds linear trajectories. A special type kinetic emerges, whose events can be analyzed combinatorially. They correspond collisions subsets points, are one-to-one correspondence contractions underlying rigid components. show how process them algorithmically via sweep. Of particular interest those planar which non-crossing motion. Our main result they (essentially) pseudo-triangulation mechanisms: pointed pseudo-trian- gulations convex hull edge removed. These structures have potential applications morphing more complex shapes than just simple polygons.