flâneur

[2309.10122] Graph Threading

arxiv.org · 9,367 words · saved by 1 readers

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.

# link_6f6i3vj36s.pdf ## Metadata - PDFFormatVersion=1.5 - IsLinearized=false - IsAcroFormPresent=false - IsXFAPresent=false - IsCollectionPresent=false - IsSignaturesPresent=false - Author=Erik D. Demaine, Yael Kirkpatrick, Rebecca Lin - CreationDate=D:20240529003710Z - Creator=LaTeX with lipics-v2021.cls - Keywords=Shortest walk, Eulerian tour, perfect matching, deployable structures, beading - ModDate=D:20240529003710Z - Custom.PTEX.Fullbanner=This is pdfTeX, Version 3.141592653-2.6-1.40.25 (TeX Live 2023) kpathsea version 6.3.5 - Producer=pdfTeX-1.40.25 - Subject=LIPIcs, Vol.287, ITCS 2024

saved by

related reading