**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.

**NC algorithms for perfect matching and maximum flow in one-crossing-minor-free graphs**.

D. Eppstein and V. V. Vazirani.

arXiv:1802.00084.

*Proc. 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019)*, Phoenix, Arizona, 2019, to appear.

We extend Anari and Vazirani's parallel algorithm for perfect matching in planar graphs to the graph families with a forbidden minor with crossing number one, by developing a concept of mimicking networks for perfect matching.

**Stable-matching Voronoi diagrams: combinatorial complexity and algorithms**.

G. Barequet, D. Eppstein, M. T. Goodrich, and N. Mamano.

arXiv:1804.09411

*Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)*, Prague.

Leibniz International Proceedings in Informatics (LIPIcs) 107, pp. 89:1–89:14.

The stable-matching Voronoi diagram of a collection of point sites in the plane, each with a specified area, is a collection of disjoint regions of the plane, one for each site and having the specified area, so that no pair of a point and a site are closer to each other than to the farthest other site and point that they may be matched to. We prove nearly-matching upper and lower bounds on the combinatorial complexity of these diagrams and provide algorithms that can compute them in a polynomial number of primitive steps.

**Realization and connectivity of the graphs of origami flat foldings**.

D. Eppstein.

arXiv:1808.06013.

*Proc. 26th Int. Symp. Graph Drawing*, Barcelona, 2018.

Springer,*Lecture Notes in Comp. Sci.*11282 (2018), pp. 541–554.If you fold a piece of paper flat and unfold it again, the resulting crease pattern forms a planar graph. We prove that a tree can be realized in this way (with its leaves as diverging rays that reach the boundary of the paper) if and only if all internal vertices have odd degree greater than two. On the other hand, for a folding pattern on an infinite sheet of paper with an added vertex at infinity as the endpoint of all its rays, the resulting graph must be 2-vertex-connected and 4-edge-connected.

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

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

arXiv:1810.08314.

A minor-closed graph family has a functional relation between diameter and path width (bounded local pathwidth) if and only if it excludes an apex-tree. The same graph families are also the ones with bounded layered pathwidth: a simultaneous path decomposition and layering (sequence of subsets of vertices with all edges connecting the same subset or consecutive subsets) so that the intersection of a bag and a layer has constant size.

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

Semi-automatically filtered from a common source file.