Computationally Intensive Puns with Figurative Subgraphs

Year: 2018 Authors: Robert Bosch

Core claim

Figurative subgraphs can be optimized to render images, with spanning trees generally matching targets better than Eulerian subgraphs and Hamiltonian cycles.

Topics

figurative graph drawing, image approximation, Hamiltonian cycles, Eulerian subgraphs, spanning trees

Domains

graph theory, combinatorial optimization, Hamiltonian cycle, Eulerian graph, spanning tree, data art, visual punning, generative art

Methods

integer programming, local search, trace model, subtour elimination, sum-of-squares minimization

Media

grayscale target images, king-knight chessboard graph, emoji portraits, Königsberg map

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2018 Conference Proceedings

Computationally Intensive Puns with Figurative Subgraphs

Robert Bosch

Oberlin College, Oberlin, Ohio, USA; rbosch@oberlin.edu

Abstract

Given a grayscale target image $I$ and a graph $G=(V,E)$ , whose vertices we have placed in fixed positions in the plane, we find subgraphs of $G$ — Hamiltonian cycles, spanning Eulerian subgraphs, and spanning trees — that closely resemble image $I$ .

Introduction

Figure 1(a) is a drawing of a graph $G=(V,E)$ that corresponds to a $16\times 16$ chessboard. The dots are the vertices, the elements of the vertex set $V$ . They represent the squares of the chessboard. The lines are the edges, the elements of the edge set $E$ . They show all the moves that a chess king or knight could make. We call $G$ the $16\times 16$ king-knight chessboard graph. Figure 1(b) displays a Hamiltonian cycle of $G$ ; if we start at the vertex in the upper left corner and go clockwise (or counterclockwise), we will end up visiting each of the other vertices once and only once before returning to where we started. Figure 1(c) displays a spanning Eulerian subgraph of $G$ . Here, because each vertex has even degree (i.e., touches an even number of edges), it is possible to start at the vertex in the upper left corner and take a walk that ends up where we started and uses each of the subgraph edges once and only once. Figure 1(d) shows a spanning tree of $G$ . This subgraph is connected and acyclic. If, once again, we start at the vertex in the upper left corner, we will be able to take a walk to any other vertex; moreover, there will be only one such walk from the origin vertex to the destination vertex.

Figure 1: (a) the $16\times 16$ king-knight chessboard graph $G$ together with (b) a Hamiltonian cycle of $G$ , (c) a spanning Eulerian subgraph of $G$ , and (d) a spanning tree of $G$ . © RB 2018.

In this paper, we present some results of our efforts to solve three related problems. Given a grayscale target image $I$ and a graph $G=(V,E)$ , whose vertices we have placed in fixed positions in the plane, we wish to find subgraphs of $G$ — Hamiltonian cycles, spanning Eulerian subgraphs, and spanning trees — that closely resemble image $I$ . The Hamiltonian-cycle version of the problem was introduced by Bosch and Wexler [1] as the Figurative Tour Problem, for if we follow a Hamiltonian cycle, we “tour” the vertices. Bosch and Wexler used integer-programming-based local search to construct their figurative tours.

Bosch

Cycles and Circuits and Trees (Oh My!)

In Bosch and Wexler’s model, there is a variable (an unknown) for each edge $e\in E$ . The variable $x_e$ takes on the value 1 if edge $e$ is in the Hamiltonian cycle, and 0 if not. There is also a variable for each square cell $s$ of the down-sampled target image $I$ . The variable $t_s$ is called the trace of the cycle on square cell $s$ and measures the total amount of ink that the cycle deposits on square cell $s$ . Bosch and Wexler use linear equations to express the $t_s$ ‘s in terms of the $x_e$ ‘s. They also include linear constraints to force the $x_e$ ‘s to give rise to a Hamiltonian cycle: degree constraints that force each vertex to be incident to precisely two edges of the cycle, as well as additional constraints that prohibit subtours. As is done in linear-programming-based approaches to the Traveling Salesman Problem [2], they impose the subtour elimination constraints as needed, in a whack-a-mole fashion. Their objective is to minimize the sum of the squares of the errors $SSE={\sum }_s(t_s-{\delta }_s{)}^2$ , where ${\delta }_s$ is a measure of the darkness of square cell $s$ in $I$ . Both the trace values and the darkness values are measured on a 0-to-100 lightest-to-darkest scale.

It is straightforward to modify Bosch and Wexler’s model to produce spanning Eulerian subgraphs or spanning trees. In the Eulerian case, the degrees must be positive and even. For spanning trees, the degrees must be positive. Figure 2(tl) displays a down-sampled target image of a sunglass-wearing emoji. Figure 2(tr) shows a Hamiltonian cycle rendition; Figure 2(bl), a spanning Eulerian subgraph version; and Figure 2(br), a spanning tree. For these figurative subgraphs, the graph G was the $32\times 32$ king-knight chessboard graph.

Figure 2: An emoji (tl) rendered as (tr) a Hamiltonian cycle, (bl) a spanning Eulerian subgraph, and (br) a spanning tree on the $32\times 32$ king-knight chessboard graph. © RB 2018.

Computationally Intensive Puns with Figurative Subgraphs

In terms of quality (recognizability), the Hamiltonian version is the worst, followed by the Eulerian, and then the spanning tree. This is consistent with the sum-of-squares values: the Hamiltonian cycle rendition has $SSE=105229$ , the spanning Eulerian subgraph rendition has $SSE=88364$ , and the spanning tree has $SSE=60331$ . To further quantify the quality of the figurative subgraphs, we computed correlations between the trace values and the darkness values. For the Hamiltonian-cycle emoji, the correlation is 0.871. For the spanning-Eulerian-subgraph emoji, it is 0.917. For the spanning-tree emoji, it is 0.943. This makes sense, as the Hamiltonian cycle degree constraints are the most restrictive, and the spanning tree constraints are the least restrictive.

Possibilities for Artistic Expression and/or Computationally Intensive Puns

In the triptych of Hamiltonian cycle portraits shown below in Figure 3, we have the great Irish mathematician William Rowan Hamilton—after whom the cycles are named—on the left. In the center and on the right, we have two other famous Hamiltons: Lin-Manuel Miranda (of the Tony-award- and Pulitzer-prize-winning musical Hamilton) and Linda Hamilton (most famous for playing Sarah Connor in James Cameron’s 1984 movie The Terminator, which was selected for preservation by the Library of Congress in 2008). For these examples, the graph G was the $64\times 64$ king-knight chessboard graph. In an effort to perform error diffusion, the objective was to minimize

In other words, the trace values and darkness values were assembled into $2\times 2$ blocks, and the goal was to minimize the sum of the squares of the $2\times 2$ errors (in place of SSE, which could also be denoted as $SS{E}_{1\times 1}$ ).

Figure 3: A triptych of Hamiltonian cycle portraits on the $64\times 64$ king-knight chessboard graph: (a) William Rowan Hamilton, (b) Lin-Manuel Miranda, and (c) Linda Hamilton. © RB 2017.

For the William cycle, the correlation between the $2\times 2$ trace values and the $2\times 2$ darkness values is 0.973. For the Lin-Manuel cycle, it is also 0.973. For the Linda cycle, it is 0.981. The $1\times 1$ correlations are 0.775, 0.710, and 0.631, respectively.

Figure 4 displays a spanning Eulerian subgraph of the $64\times 64$ king-knight chessboard graph. The target image came from a map of a well known section of the city of Königsberg. A river separates the city into four land masses: one at the top of the map, one at the bottom, and two islands. There are seven bridges that connect pairs of land masses. In 1736 Leonard Euler showed that it is impossible to take a walk that starts somewhere in Königsberg, ends at the very same place, and crosses each bridge exactly once. Such a walk

Bosch

exists if and only if each land mass touches an even number of bridges (has even degree), and here, none of them do. But in the spanning-Eulerian-subgraph rendition of the map, each vertex has degree two or four, so the subgraph is Eulerian, which means that there must exist a walk that starts at the vertex of your choice, ends there, and uses each edge of the subgraph precisely once.

Figure 4: A new solution to Euler’s Königsberg Bridge Problem. © RB 2018.

Figure 5 displays a triptych of spanning-tree renditions of a tree emoji, the mathematician Arthur Cayley (who proved a well known combinatorial result about trees), and baby Groot from Guardians of the Galaxy 2.

Figure 5: A triptych of spanning trees on the $32\times 32$ king-knight chessboard graph. © RB 2018.

References

[1] R. Bosch and T. Wexler. “Figurative Tours and Braids.” Bridges Conference Proceedings, Baltimore, USA, Jul. 29-Aug. 1, 2015, pp. 121-128. http://archive.bridgesmathart.org/2015/bridges2015-121. [2] W.J. Cook. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, 2012.