**Reference**:- Erik D. Demaine, Yael Kirkpatrick, and Rebecca Lin, “Graph Threading”, in
*Proceedings of the 15th Conference on Innovations in Theoretical Computer Science (ITCS 2024)*, LIPIcs, Berkeley, California, 2024, 38:1–38:18. **Abstract**:-
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. **Comments**:- This paper is also available from LIPIcs.
**Length**:- The paper is 18 pages.
**Availability**:- The paper is available in PDF (4406k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated February 26, 2024 by Erik Demaine.