**Convex-arc drawings of pseudolines**.

D. Eppstein, M. van Garderen, B. Speckmann, and T. Ueckerdt.

*21st Int. Symp. Graph Drawing*(poster), Bordeaux, France, 2013.

Springer,*Lecture Notes in Comp. Sci.*8242, 2013, pp. 522–523.

arXiv:1601.06865.

We show that every outerplanar weak pseudoline arrangement (a collection of curves topologically equivalent to lines, each crossing at most once but possibly zero times, with all crossings belonging to an infinite face) can be straightened to a hyperbolic line arrangement. As a consequence such an arrangement can also be drawn in the Euclidean plane with each pseudoline represented as a convex piecewise-linear curve with at most two bends. In contrast, for arbitrary pseudoline arrangements, a linear number of bends is sufficient and sometimes necessary.

**Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect**.

J. Cardinal, E. Demaine, D. Eppstein, R. Hearn, and A. Winslow.

arXiv:1805.04055

*Proc. 24th International Computing and Combinatorics Conference (COCOON 2018)*, Qingdao, China.

Springer,*Lecture Notes in Comp. Sci.*10976 (2018), pp. 365–377.For several problems with polynomial-time solutions, we show that finding a sequence of steps that converts one solution into another (maintaining a valid solution at each step) is hard. These include planar monotone not-all-equal 3-sat, subset sum on integers of polynomial magnitude, and 0-1 integer programming with a constant number of linear inequality constraints.

(Slides)

**Minor-closed graph classes with bounded layered pathwidth**.

V. Dujmović, D. Eppstein, G. Joret, P. Morin, and D. R. Wood.

arXiv:1810.08314.

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

Semi-automatically filtered from a common source file.