Depian, T., Haase, C., Nöllenburg, M., & Schulz, A. (2025). On Planar Unit-Length Linear Linkages in Polygonal Domains. In EUROCG’25 Booklet of Abstracts. EuroCG 2025, Liblice, Czechia. http://hdl.handle.net/20.500.12708/225309
E192-01 - Forschungsbereich Algorithms and Complexity
-
Published in:
EUROCG'25 Booklet of Abstracts
-
Date (published):
Apr-2025
-
Event name:
EuroCG 2025
en
Event date:
9-Apr-2025 - 11-Apr-2025
-
Event place:
Liblice, Czechia
-
Number of Pages:
9
-
Peer reviewed:
Yes
-
Keywords:
graph linkage; polygons; planar graphs
en
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.
