Realizing Planar Linkages in Polygonal Domains

arXiv:2604.05786 · cs.CG · Submitted 2026-04-07 · Read on arXiv

cs.CG

Submitted: 2026-04-07

Updated: 2026-11-14

Comments: 35 pages, 14 figures

License: http://creativecommons.org/licenses/by/4.0/

The gist: A linkage L consists of a graph G=(V,E) and an edge-length function.

Terminology

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 squared with edge length (e) for all e in 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 that the problem is in XP parameterized by the size of G, and W[1]-hard even if 1 and no vertex positions are constrained. Furthermore, we consider the case where G is a path with constrained start and end position and 1. Despite the absence of any rigid components, we obtain NP-hardness in general, and provide a O(n n) time algorithm for n being the number of vertices of P for arbitrary if G has only three edges, both endpoints are constrained, and P is convex.

Related papers