**The parametric closure problem**.

D. Eppstein.

arXiv:1504.04073.

14th Algorithms and Data Structures Symp. (WADS 2015), Victoria, BC.

Springer,*Lecture Notes in Comp. Sci.*9214 (2015), pp. 327–338.

*ACM Trans. Algorithms*, to appear.We consider the minimum weight closure problem for a partially ordered set whose elements have weights that vary linearly as a function of a parameter. For several important classes of partial orders the number of changes to the optimal solution as the parameter varies is near-linear, and the sequence of optimal solutions can be found in near-linear time.

(Slides)

**Folding polyominoes into (poly)cubes**.

O. Aichholzer, M. Biro, E. Demaine, M. Demaine, D. Eppstein, S. P. Fekete, A. Hesterberg, I. Kostitsyna, and C. Schmidt.

*27th Canadian Conference on Computational Geometry*, Kingston, Ontario, Canada, 2015, pp. 101–106.

*Int. J. Comp. Geom. & Appl.*, to appear.We classify the polyominoes that can be folded to form the surface of a cube or polycube, in multiple different folding models that incorporate the type of fold (mountain or valley), the location of a fold (edges of the polycube only, or elsewhere such as along diagonals), and whether the folded polyomino is allowed to pass through the interior of the polycube or must stay on its surface.

**On the planar split thickness of graphs**.

D. Eppstein, P. Kindermann, S. G. Kobourov, G. Liotta, A. Lubiw, A. Maignan, D. Mondal, H. Vosoughpour, S. Whitesides, and S. Wismath.

arXiv:1512.04839.

*Proc. 12th Latin American Theoretical Informatics Symposium (LATIN 2016)*, Ensenada, Mexico.

Springer,*Lecture Notes in Comp. Sci.*9644 (2016), pp. 403–415.

*Algorithmica*, to appear.We study the problem of splitting the vertices of a given graph into a bounded number of sub-vertices (with each edge attaching to one of the sub-vertices) in order to make the resulting graph planar. It is NP-complete, but can be approximated to within a constant factor, and is fixed-parameter tractable in the treewidth.

(Slides)

**From discrepancy to majority**.

D. Eppstein and D. S. Hirschberg.

arXiv:1512.06488.

*Proc. 12th Latin American Theoretical Informatics Symposium (LATIN 2016)*, Ensenada, Mexico.

Springer,*Lecture Notes in Comp. Sci.*9644 (2016), pp. 390–402.

*Algorithmica*, to appear.We provide upper and lower bounds on the query complexity of a problem in which the input is a collection of two-colored items, and the problem is to either find an item of the majority color or to determine that there is no majority, by performing queries that determine the discrepancy of fixed-size subsets of the items.

(Slides)

Years – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.