### 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 study a graph reordering problem motivated by compressing massive graphs such as social networks and inverted indexes. Given a graph, *G *= (*V*, *E*), the *Minimum Logarithmic Arrangement* problem is to find a permutation, π, of the vertices that minimizes

∑ (1 + ⌊lg |π(u) − π(v)|⌋). (u,v)∈E

This objective has been shown to be a good measure of how many bits are needed to encode the graph if the adjacency list of each vertex is encoded using relative positions of two consecutive neighbors under the *π* order in the list rather than using absolute indices or node identifiers, which requires at least lg *n* bits per edge. We show the first non-trivial approximation factor for this problem by giving a polynomial time *O*(log *k*)-approximation algorithm for graphs with treewidth *k*.

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é