Graphs with flexible labelings allowing injective realizations

DOI10.1016/J.DISC.2019.111713zbMATH Open1437.05206arXiv1811.06709OpenAlexW2901405133WikidataQ114190672 ScholiaQ114190672MaRDI QIDQ2174572FDOQ2174572

Authors: Georg Grasegger, Jan Legerský, Josef Schicho 

Publication date: 21 April 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We consider realizations of a graph in the plane such that the distances between adjacent vertices satisfy the constraints given by an edge labeling. If there are infinitely many such realizations, counted modulo rigid motions, the labeling is called flexible. The existence of a flexible labeling, possibly non-generic, has been characterized combinatorially by the existence of a so called NAC-coloring. Nevertheless, the corresponding realizations are often non-injective. In this paper, we focus on flexible labelings with infinitely many injective realizations. We provide a necessary combinatorial condition on existence of such a labeling based also on NAC-colorings of the graph. By introducing new tools for the construction of such labelings, we show that the necessary condition is also sufficient up to 8 vertices, but this is not true in general for more vertices.

Full work available at URL: https://arxiv.org/abs/1811.06709

Recommendations

• Graphs with flexible labelings
• Global rigidity of (quasi-)injective frameworks on the line
• On the classification of motions of paradoxically movable graphs
• Flexibility and movability in Cayley graphs
• Flexible placements of periodic graphs in the plane

zbMATH Keywords

rigidityflexibilitylinkagegraph realizationLaman graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• The number of realizations of a Laman graph
• On graphs and rigidity of plane skeletal structures
• Lectures on the theory of algebraic functions of one variable
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graphs with flexible labelings
• When does a planar bipartite framework admit a continuous deformation?
• Title not available (Why is that?)

Cited In (12)

• Flexible placements of periodic graphs in the plane
• Flexibility and movability in Cayley graphs
• Global rigidity of (quasi-)injective frameworks on the line
• On the Existence of Paradoxical Motions of Generically Rigid Graphs on the Sphere
• Title not available (Why is that?)
• Four-bar linkages, elliptic functions, and flexible polyhedra
• On the classification of motions of paradoxically movable graphs
• FlexRiLoG -- a SageMath package for motions of graphs
• Flexible placements of graphs with rotational symmetry
• Flexing infinite frameworks with applications to braced Penrose tilings
• Injective envelope of graphs and transition systems
• And yet it moves: paradoxically moving linkages in kinematics

Uses Software

• FlexRiLoG
• LamanGraphs

This page was built for publication: Graphs with flexible labelings allowing injective realizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174572)