Graphs with flexible labelings allowing injective realizations

DOI10.1016/J.DISC.2019.111713MaRDI QIDQ2174572zbMATH OpenOpenAlexWikidataFDO

Authors Georg Grasegger, Jan Legerský, Josef Schicho

Publication date 21 April 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3526316 (Why is no real title available?)
• scientific article; zbMATH DE number 1454640 (Why is no real title available?)
• scientific article; zbMATH DE number 3087419 (Why is no real title available?)
• Graphs with flexible labelings
• Lectures on the theory of algebraic functions of one variable
• On graphs and rigidity of plane skeletal structures
• The number of realizations of a Laman graph
• When does a planar bipartite framework admit a continuous deformation?

Cited in

(13)

• And yet it moves: paradoxically moving linkages in kinematics
• Graphs with flexible labelings
• 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
• Four-bar linkages, elliptic functions, and flexible polyhedra
• scientific article; zbMATH DE number 6383834 (Why is no real title available?)
• On the classification of motions of paradoxically movable graphs
• FlexRiLoG -- a SageMath package for motions of graphs
• Injective envelope of graphs and transition systems
• Flexible placements of graphs with rotational symmetry
• Flexing infinite frameworks with applications to braced Penrose tilings

Describes a project that uses

Uses Software

• LamanGraphs
• FlexRiLoG

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)