From String to Structure: Graph Threading for Physical Assembly

Abstract

Many artistic and engineering applications—from beadwork to deployable structures—create intricate, and sometimes dynamic, designs by threading cord through tubular components. We model the underlying design challenge—threading tubes so that they achieve a target connectivity when the string is pulled taut—as graph threading. In this formulation, tubes and their junctions correspond to edges and vertices of a graph, and the goal is to find a closed walk that induces a connected graph at every vertex while avoiding U-turns. We study two optimization objectives motivated by fabrication and deployment: minimizing length to reduce material cost and assembly time, and minimizing turn to reduce frictional resistance during deployment. For the length metric, we present a polynomial-time algorithm via reduction to minimum-weight perfect matching, prove tight worst-case bounds on optimal threadings, and identify special cases with faster algorithms. For the turn metric, we characterize the complexity landscape, proving NP-hardness for graphs of maximum degree 4, tractability for degree 3, and giving exact and approximation algorithms for restricted variants, including rectangular grid graphs. Finally, we turn from theory to fabrication, proposing multi-configuration threading—a new approach for achieving multiple predetermined configurations within a single system. As in earlier chapters, framing the problem in graph-theoretical terms provides access to powerful problem-solving techniques, guiding both algorithmic analysis and physical design.