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

flexibilitygraph realizationLaman graphlinkagerigidity

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

• Graphs with flexible labelings
• 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?)
• 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

(16)

• Injective envelope of graphs and transition systems
• Flexible placements of graphs with rotational symmetry
• Flexing infinite frameworks with applications to braced Penrose tilings
• Flexibility and movability in Cayley graphs
• Four-bar linkages, elliptic functions, and flexible polyhedra
• Graphs with flexible labelings
• Flexible placements of periodic graphs in the plane
• Global rigidity of (quasi-)injective frameworks on the line
• 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
• On the Existence of Paradoxical Motions of Generically Rigid Graphs on the Sphere
• And yet it moves: paradoxically moving linkages in kinematics
• Constrained cubic grid rigidity decision with directed graph and applications
• Constructing reflection-symmetric flexible realisations of graphs
• Stable cuts, NAC-colourings and flexible realisations of graphs

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)