Figurative Tours and Braids

Robert Bosch and Tom Wexler
Proceedings of Bridges 2015: Mathematics, Music, Art, Architecture, Culture (2015)
Pages 121–128 Regular Papers


We start with a rectangular grid of points, and we connect pairs of points to form either a tour (a Hamiltonian cycle) or a braid (a collection of disjoint paths that start in the top row and end on the bottom). In each case, our goal is to design a graph that will closely resemble a grayscale target image when viewed from a distance. From up close, the graph will look like an abstract pattern. We formulate these design problems as integer programming problems.