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

**Flat foldings of plane graphs with prescribed angles and edge lengths**.

Z. Abel, E. Demaine, M. Demaine, D. Eppstein, A. Lubiw, and R. Uehara.

arXiv:1408.6771.

*22nd Int. Symp. Graph Drawing*, Würzburg, Germany, 2014.

Springer,*Lecture Notes in Comp. Sci.*8871, 2014, pp. 272–283.

*J. Computational Geometry*9 (1): 71–91, 2018.Given a plane graph with fixed edge lengths, and an assignment of the angles 0, 180, and 360 to the angles between adjacent edges, we show how to test whether the angle assignment can be realized by an embedding of the graph as a flat folding on a line. As a consequence, we can determine whether two-dimensional cell complexes with one vertex can be flattened. The main idea behind the result is to show that each face of the graph can be folded independently of the other faces.

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

**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*80 (4): 1278–1297, 2018.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)

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

*J. Graph Algorithms & Applications*, to appear.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.

*J. Graph Algorithms & Applications*, to appear.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.

arXiv:1805.05443.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.

*Experimental Mathematics*, to appear.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.

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

D. Eppstein and V. V. Vazirani.

arXiv:1802.00084.

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.

**Reactive proximity data structures for graphs**.

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

arXiv:1803.04555.

*Proc. 13th Latin American Theoretical Informatics Symposium (LATIN 2018)*, Buenos Aires, Argentina.

Springer,*Lecture Notes in Comp. Sci.*10807 (2018), pp. 777–789.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).

**Subexponential-time and FPT algorithms for embedded flat clustered planarity**.

G. Da Lozza, D. Eppstein, M. T. Goodrich, and S. Gupta.

arXiv:1803.05465

*Proc. 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018)*, Lübbenau, Germany, to appear.

Clustered planarity is the problem of simultaneously drawing a planar graph and a clustering of its vertices (as Jordan curves surrounding the cluster) with no unnecessary crossings between edges or cluster boundaries; it remains unknown whether it can be solved in polynomial time. We provide parameterized and subexponential exact algorithms for the case where the planar embedding is fixed and the clusters form a partition of the vertices.

**Faster evaluation of subtraction games**.

D. Eppstein.

arXiv:1804.06515.

*Proc. 9th Int. Conf. Fun with Algorithms (FUN 2018)*, La Maddalena, Italy, to appear.

We show how to evaluate the set of winning heap sizes in subtraction games like subtract-a-square in near-linear time, and how to compute the nim-values more quickly than naive dynamic programming. Additionally we perform computational experiments showing that the set of winning positions forms an unexpectedly dense square-difference-free set.

**Making change in 2048**.

D. Eppstein.

arXiv:1804.07396.

*Proc. 9th Int. Conf. Fun with Algorithms (FUN 2018)*, La Maddalena, Italy, to appear.

The 2048 puzzle, modified to use any sequence of integer tile values that has arbitrarily large gaps, always terminates. The proof relates the puzzle to the greedy algorithm for making change (suboptimally) using a given system of coins.

**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, to appear.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.

**Optimally sorting evolving data**.

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

arXiv:1805.03350

*Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)*, Prague, to appear.Suppose that a collection of objects has a linear order that is evolving by swaps of randomly chosen consecutive elements. We would like to maintain an approximation to this order using an algorithm that performs one comparison per swap. We show that repeated insertion sort can maintain linear inversion distance from the underlying order, the best possible.

**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, to appear.

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.

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

Semi-automatically filtered from a common source file.