Realizing Planar Linkages in Polygonal Domains
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
- The Rhythm of the Tiles: Narrow and Low Temperature Computation and Simulation in Synchronous Tile Self-Assembly
- Covering Points with Rectangular Boundaries
- Tiling 3D Space by (Translates of) a Single Polycube is Undecidable
- Quadratic Complexity of Voronoi Diagrams in R cubed for Lines in a Single Ruling of a Regulus
- Minimum central circles: chain order, seam obstructions, and exact finite certification
- One Shot, Twenty-One Balls: A Computer-Assisted Proof of a Single-Stroke Total Clearance in an Idealized Model of Snooker