2026-08-09T04:21:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19566 2024-03-06T11:04:20Z ddc:004 open_access

Graph Threading Demaine, Erik D. Kirkpatrick, Yael Lin, Rebecca Shortest walk Eulerian cycle perfect matching beading Inspired by artistic practices such as beadwork and himmeli, we study the problem of threading a single string through a set of tubes, so that pulling the string forms a desired graph. More precisely, given a connected graph (where edges represent tubes and vertices represent junctions where they meet), we give a polynomial-time algorithm to find a minimum-length closed walk (representing a threading of string) that induces a connected graph of string at every junction. The algorithm is based on a surprising reduction to minimum-weight perfect matching. Along the way, we give tight worst-case bounds on the length of the optimal threading and on the maximum number of times this threading can visit a single edge. We also give more efficient solutions to two special cases: cubic graphs and the case when each edge can be visited at most twice. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Erik D. Demaine and Yael Kirkpatrick and Rebecca Lin 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.38 urn:nbn:de:0030-drops-195665 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.38 eng https://creativecommons.org/licenses/by/4.0/legalcode