{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreif2cqgpy4qhewpook7th7ytrtt5djynwehr4cfh7zpekgyjcf7zwa",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mixhkqvx5dr2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.05786v1",
  "publishedAt": "2026-04-08T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Thomas Depian",
    "Carolina Haase",
    "Martin Nöllenburg",
    "André Schulz"
  ],
  "textContent": "**Authors:** Thomas Depian, Carolina Haase, Martin Nöllenburg, André Schulz\n\nA linkage $\\mathcal{L}$ consists of a graph $G=(V,E)$ and an edge-length function $\\ell$. Deciding whether $\\mathcal{L}$ can be realized as a planar straight-line embedding in $\\mathbb{R}^2$ with edge length $\\ell(e)$ for all $e \\in E$ is $\\exists\\mathbb{R}$-complete [Abel et al., JoCG'25], even if $\\ell \\equiv 1$, but a considerable part of $\\mathcal{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 $\\ell \\equiv 1$ and no vertex positions are prescribed. Furthermore, we consider the case where $G$ is a path with prescribed start and end position and $\\ell \\equiv 1$. Despite the absence of any rigid components, we obtain NP-hardness in general, and provide a linear-time algorithm for arbitrary $\\ell$ if $G$ has only three edges and $P$ is convex.",
  "title": "Realizing Planar Linkages in Polygonal Domains"
}