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, January 30–February 2, 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]