**Parameterized complexity of 1-planarity**.

M. J. Bannister, S. Cabello, and D. Eppstein.

arXiv:1304.5591.

13th Int. Symp. Algorithms and Data Structures (WADS 2013), London, Ontario

Springer,*Lecture Notes in Comp. Sci. 8037*, 2013, pp. 97–108.

*J. Graph Algorithms and Applications*18 (1): 23–49, 2018. (Special issue on Graph Drawing Beyond Planarity.)

We show that testing whether a graph is 1-planar (drawable with at most one crossing per edge) may be performed in polynomial and fixed-parameter tractable time for graphs of bounded circuit rank, vertex cover number, or tree-depth. However, it is NP-complete for graphs of bounded treewidth, pathwidth, or bandwidth.

(Slides)

**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*14 (1): Article 2, 2018.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)

**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*80 (3): 977–994 (special issue for LATIN), 2018.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)

**Triangle-free penny graphs: degeneracy, choosability, and edge count**.

D. Eppstein.

arXiv:1708.05152.

*Proc. 25th Int. Symp. Graph Drawing*, Boston, Massachusetts, 2017.

Springer,*Lecture Notes in Comp. Sci.*10692 (2018), pp. 506–513.A penny graph is the contact graph of unit disks: each disk represents a vertex of the graph, no two disks can overlap, and each tangency between two disks represents an edge in the graph. We prove that, when this graph is triangle free, its degeneracy is at most two. As a consequence, triangle-free penny graphs have list chromatic number at most three. We also show that the number of edges in any such graph is at most 2

*n*− Ω(√*n*).(Slides)

**The effect of planarization on width**.

D. Eppstein.

arXiv:1708.05155.

*Proc. 25th Int. Symp. Graph Drawing*, Boston, Massachusetts, 2017.

Springer,*Lecture Notes in Comp. Sci.*10692 (2018), pp. 560–572.We study what happens to nonplanar graphs of low width (for various width measures) when they are made planar by replacing crossings by vertices. For treewidth, pathwidth, branchwidth, clique-width, and tree-depth, this replacement can blow up the width from constant to linear. However, for bandwidth, cutwidth, and carving width, graphs of bounded width stay bounded when we planarize them.

(Slides)

**Quadratic time algorithms appear to be optimal for sorting evolving data**.

J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.

*Proc. Algorithm Engineering & Experiments (ALENEX 2018)*, New Orleans, 2018, pp. 87–96.

We experiment with sorting algorithms in the evolving data model, in which, at the same time as the algorithm compares pairs of elements and possibly chooses a new ordering based on the results of the comparison, an adversary randomly chooses two adjacent elements in the sorted order and swaps them. As we show, bubble sort and its variants appear to maintain an order that is within inversion distance of optimal.

**Grid peeling and the affine curve-shortening flow**.

D. Eppstein, S. Har-Peled, and G. Nivasch.

*Proc. Algorithm Engineering & Experiments (ALENEX 2018)*, New Orleans, 2018, pp. 109–116.We conjecture, based on experiments, that approximating a convex shape by the set of grid points inside it, for a fine enough grid, and then finding the convex layers of the resulting point set, produces curves that are close to those produced by affine curve-shortening, a continuous process on smooth curves.

**Reactive Proximity Data Structures for Graphs**.

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

*Proc. 13th Latin American Theoretical Informatics Symposium (LATIN 2018)*, Buenos Aires, Argentina, to appear.We develop data structures for solving nearest neighbor queries for dynamic subsets of vertices in a planar graph, or more generally for a graph in any graph class with small separators (polynomial expansion).

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

Semi-automatically filtered from a common source file.