### A Method for Animating Children’s Drawings of the Human Figure

Harrison Jesse Smith, Qingyuan Zheng, Yifei Li, Somya Jain, Jessica K. Hodgins

International Symposium on Algorithms and Computation (ISAAC )

We initiate the theoretical study of Ext-TSP, a problem that originates in the area of profile-guided binary optimization. Given a graph *G = (V, E)* with positive edge weights *w* : *E→R*^{+} , and a non-increasing discount function *ƒ *(·) such that *ƒ *(1) = 1 and ƒ (*i*) = 0 for *i* > *k*, for some parameter *k* that is part of the problem definition. The problem is to sequence the vertices *V* so as to maximize ∑_{(u, v)∈E }ƒ(|d_{u} — d_{v }|) ⋅ *w *(*u, v *), where *d*_{v} ∈ {1, . . . , |V|} is the position of vertex *v* in the sequence.

We show that Ext-TSP is APX-hard to approximate in general and we give a (*k* + 1)- approximation algorithm for general graphs and a PTAS for some sparse graph classes such as planar or treewidth-bounded graphs.

Interestingly, the problem remains challenging even on very simple graph classes; indeed, there is no exact n^{o (k)} time algorithm for trees unless the ETH fails. We complement this negative result with an exact n^{O(k)} time algorithm for trees.

Harrison Jesse Smith, Qingyuan Zheng, Yifei Li, Somya Jain, Jessica K. Hodgins

Yunbo Zhang, Deepak Gopinath, Yuting Ye, Jessica Hodgins, Greg Turk, Jungdam Won

Simran Arora, Patrick Lewis, Angela Fan, Jacob Kahn, Christopher Ré