Paper by Erik D. Demaine

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]