About

David Eppstein is a Distinguished Professor of Computer Science at UC Irvine's Donald Bren School of Information & Computer Sciences. He earned his Ph.D. in Computer Science from Columbia University in 1989 and his B.S. in Mathematics from Stanford University in 1984. His research interests include graph algorithms, graph theory, discrete and computational geometry, graph drawing and information visualization, and data structures. Eppstein has been recognized as a Fellow of the ACM in 2012, a Fellow of the AAAS in 2017, and was named a Distinguished Professor in 2020. His work has earned him several awards, including the SIAM Best Paper Award in 2022. He is known for his contributions to algorithm design and computational complexity theory, and he has been involved in collaborative research projects, including a $1.2 million NSF grant studying geometric graphs.

Research topics

• Computer Science
• Mathematics
• Humanities
• Artificial Intelligence
• Combinatorics
• Theoretical computer science
• Discrete mathematics
• Algorithm

Selected publications

• Noncrossing Longest Paths and Cycles

  Graphs and Combinatorics · 2025-10-27

  preprintOpen access
  PublisherOA PDFDOI

• Computational Complexities of Folding

  Journal of Information Processing · 2025-01-01

  articleOpen access1st authorCorresponding

  We prove several hardness results on folding origami crease patterns. Flat-folding finite crease patterns is fixed-parameter tractable in the ply of the folded pattern (how many layers overlap at any point) and the treewidth of an associated cell adjacency graph. Under the exponential time hypothesis, the singly-exponential dependence of our algorithm on treewidth is necessary, even for bounded ply. Improving the dependence on ply would require progress on the unsolved map folding problem. Finding the shape of a polyhedron folded from a net with triangular faces and integer edge lengths is not possible in algebraic computation tree models of computation that at each tree node allow either the computation of arbitrary integer roots of real numbers, or the extraction of roots of polynomials with bounded degree and integer coefficients. For a model of reconfigurable origami with origami squares are attached at one edge by a hinge to a rigid surface, moving from one flat-folded state to another by changing the position of one square at a time is PSPACE-complete, and counting flat-folded states is #P-complete. For self-similar square crease patterns with infinitely many folds, testing flat-foldability is undecidable.

  PublisherOA PDFDOI

• Hamiltonian Cycles in Subdivided Doubles

  ArXiv.org · 2025-10-21

  preprintOpen access1st authorCorresponding

  The subdivided double construction on 4-regular graphs was used by Potočnik and Wilson to explore semi-symmetric (edge-transitive but not vertex-transitive) graphs, and can be used to construct every semi-symmetric 4-regular graph that contains a pair of twin vertices. We show that (regardless of symmetry) subdivided doubles have another curious property: they have exponentially many Hamiltonian cycles each of which is complementary to another Hamiltonian cycle.

  PublisherOA PDFDOI

• Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing

  ArXiv.org · 2025-05-16

  preprintOpen access1st authorCorresponding

  We provide the first approximation quality guarantees for the Cuthull-McKee heuristic for reordering symmetric matrices to have low bandwidth, and we provide an algorithm for reconstructing bounded-bandwidth graphs from distance oracles with near-linear query complexity. To prove these results we introduce a new width parameter, BFS width, and we prove polylogarithmic upper and lower bounds on the BFS width of graphs of bounded bandwidth. Unlike other width parameters, such as bandwidth, pathwidth, and treewidth, BFS width can easily be computed in polynomial time. Bounded BFS width implies bounded bandwidth, pathwidth, and treewidth, which in turn imply fixed-parameter tractable algorithms for many problems that are NP-hard for general graphs. In addition to their applications to matrix ordering, we also provide applications of BFS width to graph reconstruction, to reconstruct graphs from distance queries, and graph drawing, to construct arc diagrams of small height.

  PublisherOA PDFDOI

• Better Late than Never: the Complexity of Arrangements of Polyhedra

  ArXiv.org · 2025-06-04

  preprintOpen access

  Let $\mathcal{A}$ be the subdivision of $\mathbb{R}^d$ induced by $m$ convex polyhedra having $n$ facets in total. We prove that $\mathcal{A}$ has combinatorial complexity $O(m^{\lceil d/2 \rceil} n^{\lfloor d/2 \rfloor})$ and that this bound is tight. The bound is mentioned several times in the literature, but no proof for arbitrary dimension has been published before.

  PublisherOA PDFDOI

• Hamiltonian cycles in subdivided doubles

  Ars Mathematica Contemporanea · 2025-11-06

  articleOpen access1st authorCorresponding

  The subdivided double construction on 4-regular graphs was used by Potočnik and Wilson to explore semi-symmetric graphs. It preserves the property of being semi-symmetric, and can be used to construct every semi-symmetric 4-regular graph that contains a pair of twin vertices. We show that (regardless of symmetry) subdivided doubles have another curious property: each of their many Hamiltonian cycles is complementary to another Hamiltonian cycle.

  PublisherOA PDFDOI

• Zip-Tries: Simple Dynamic Data Structures for Strings

  Society for Industrial and Applied Mathematics eBooks · 2025-01-01

  book-chapterOpen access1st authorCorresponding

  In this paper, we introduce zip-tries, which are simple, dynamic, memory-efficient data structures for strings. Zip-tries support search and update operations for k-length strings in 𝕆(κ + log n ) time in the standard RAM model or in 𝕆(κ/α + log n ) time in the word RAM model, where α is the length of the longest string that can fit in a memory word, and n is the number of strings in the trie. Importantly, we show how zip-tries can achieve this while only requiring bits of metadata per node w.h.p., which is an exponential improvement over previous results for long strings. Despite being considerably simpler and more memory efficient, we show how zip- tries perform competitively with state-of-the-art data structures on large datasets of long strings.

  PublisherOA PDFDOI

• Decremental Greedy Polygons and Polyhedra Without Sharp Angles

  ArXiv.org · 2025-07-06

  articleOpen access1st authorCorresponding

  We show that the max-min-angle polygon in a planar point set can be found in time $O(n\log n)$ and a max-min-solid-angle convex polyhedron in a three-dimensional point set can be found in time $O(n^2)$. We also study the maxmin-angle polygonal curve in 3d, which we show to be $\mathsf{NP}$-hard to find if repetitions are forbidden but can be found in near-cubic time if repeated vertices or line segments are allowed, by reducing the problem to finding a bottleneck cycle in a graph. We formalize a class of problems on which a decremental greedy algorithm can be guaranteed to find an optimal solution, generalizing our max-min-angle and bottleneck cycle algorithms, together with a known algorithm for graph degeneracy.

  PublisherOA PDF

• Computational Geometry with Probabilistically Noisy Primitive Operations

  ArXiv.org · 2025-01-01

  preprintOpen access1st authorCorresponding

  Much prior work has been done on designing computational geometry algorithms that handle input degeneracies, data imprecision, and arithmetic round-off errors. We take a new approach, inspired by the noisy sorting literature, and study computational geometry algorithms subject to noisy Boolean primitive operations in which, e.g., the comparison "is point q above line 𝓁?" returns the wrong answer with some fixed probability. We propose a novel technique called path-guided pushdown random walks that generalizes the results of noisy sorting. We apply this technique to solve point-location, plane-sweep, convex hulls in 2D and 3D, and Delaunay triangulations for noisy primitives in optimal time with high probability.

  PublisherOA PDFDOI

• Geodesic Paths Passing Through All Faces on A Polyhedron

  Lecture notes in computer science · 2025-08-10

  book-chapter
  PublisherDOI

Recent grants

• AF:SMALL:Sparse Geometric Graph Algorithms

  NSF · $416k · 2016–2020

• Geometrics Algorithms in Statistics, Meshing, and Parametric Optimization

  NSF · $222k · 2000–2004

• AF: Small: Collaborative Research: Efficient Algorithms for Cycles on Surfaces

  NSF · $160k · 2016–2019

• AF:Small:Geometric graph algorithms

  NSF · $389k · 2012–2017

Frequent coauthors

• Michael T. Goodrich

  University of California, Irvine

  134 shared

• Giuseppe F. Italiano

  58 shared

• Zvi Galil

  Georgia Institute of Technology

  57 shared

• Marshall Bern

  50 shared

• Raffaele Giancarlo

  University of Palermo

  45 shared

• Erik D. Demaine

  38 shared

• Michael J. Bannister

  University of California, Irvine

  31 shared

• Stephen Kobourov

  University of Arizona

  23 shared

Education

• Ph.D., Computer Science

  University of California, Irvine

  1989

• M.S., Computer Science

  University of California, Irvine

  1984

• B.S., Computer Science

  University of California, Irvine

  1982

Awards & honors

• Fellow of the ACM (2012)
• Fellow of the AAAS (2017)
• Distinguished Professor (2020)
• Best Paper Award for 'On the Biplanarity of Blowups' (2023)
• SIAM Best Paper Award (2022)