On Planar Unit-Length Linear Linkages in Polygonal Domains

Abstract

A linkage L is given by a graph G and a function ℓ specifying the length of the edges in G. It is ∃R-complete to decide if L has a planar embedding with straight-line edges [Abel et al., SoCG’16]. The reduction uses unit-length edges, but G needs to have 3-connected blocks. Here, we consider the problem of finding a planar embedding of L inside a polygonal domain P when G is a path with prescribed start and end point and ℓ ≡ 1. Despite the restricted setup, we show NP-hardness for the general setting and provide an efficient algorithm if G has three edges and P is convex.