Realizing Planar Linkages in Polygonal Domains

Abstract

A linkage L consists of a graph G=(V,E) and an edge-length function ℓ. Deciding whether L can be realized as a planar straight-line embedding in R² with edge length ℓ(e) for all e∈E is ∃R-complete [Abel et al., JoCG’25], even if ℓ≡1, but a considerable part of L is rigid. In this paper, we study the computational complexity of the realization question for structurally simpler, less rigid linkages inside an open polygonal domain P, where the placement of some vertices may be specified in the input. We show XP-membership and W[1]-hardness with respect to the size of G, even if ℓ≡1 and no vertex positions are prescribed. Furthermore, we consider the case where G is a path with prescribed start and end position and ℓ≡1. Despite the absence of any rigid components, we obtain NP-hardness in general, and provide a linear-time algorithm for arbitrary ℓ if G has only three edges and P is convex.