Selected publications
Sparse dynamic programming.
D. Eppstein, Z. Galil, R. Giancarlo, and G.F. Italiano.
1st ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1990, pp. 513–522.
"Sparse dynamic programming I: linear cost functions", J. ACM 39: 519–545, 1992.
"Sparse dynamic programming II: convex and concave cost functions", J. ACM 39: 546–567, 1992.Considers sequence alignment and RNA structure problems in which the solution is constructed by piecing together some initial set of fragments (e.g. short sequences that match exactly). The method is to consider a planar point set formed by the fragment positions in the two input sequences, and use plane sweep to construct a cellular decomposition of the plane similar to the rectilinear Voronoi diagram.
Provably good mesh generation.
M. Bern, D. Eppstein, and J. Gilbert.
31st IEEE Symp. Foundations of Comp. Sci., St. Louis, Missouri, 1990, pp. 231–241.
J. Comp. Sys. Sci. 48: 384–409, 1994 (special issue for 31st FOCS).In this paper, we construct triangulations of point sets and polygons by using quadtrees to add extra vertices to the input. As a result we can guarantee that all triangles have angles bounded away from zero, using a number of triangles within a constant of optimal; this was the first paper to provide simultaneous bounds on mesh element quality and mesh complexity of this form, and therefore the first to provide finite element mesh generation algorithms that guarantee both the robustness of the algorithm against unexpected input geometries and the quality of its output.
In the same paper we also use quadtrees to triangulate planar point sets so that all angles are non-obtuse, using linearly many triangles, and to triangulate higher dimensional point sets with no small solid angles and a number of simplices within a constant of optimal. Also, we can augment any higher dimensional point set so the Delaunay triangulation has linear complexity.
In later follow-up work, I showed that the same technique can also be used to find a triangulation whose edges have total length within a constant factor of optimal. Bern, Mitchell, and Ruppert showed that alternative methods can be used to triangulate any polygon without obtuse angles; see "Faster circle packing with application to nonobtuse triangulation" for an algorithmic improvement to their technique. Additionally, with Bern, Chew, and Ruppert, we showed that any point set in higher dimensions can be triangulated with nonobtuse simplices. Bern and I surveyed these and related results in our paper "Mesh generation and optimal triangulation".
Dynamic Euclidean minimum spanning trees and extrema of binary functions.
D. Eppstein.
Tech. Rep. 92-05, ICS, UCI, 1992.
Tech. Rep. 92-88, ICS, UCI, 1992.
Disc. Comp. Geom. 13: 111–122, 1995.Shows that bichromatic nearest neighbors can be maintained under point insertion and deletion essentially as quickly as known solutions to the post office problem, and that the minimum spanning tree can be maintained in the same time except for an additive O(sqrt n) needed for solving the corresponding graph problem. TR 92-88's title was actually "Fully dynamic maintenance of Euclidean minimum spanning trees and maxima of decomposable functions". TR 92-05's title left out the part about maxima; that version gave a slower algorithm superseded by the result in 92-88.
Sparsification—A technique for speeding up dynamic graph algorithms.
D. Eppstein, Z. Galil, G.F. Italiano, and A. Nissenzweig.
33rd IEEE Symp. Foundations of Comp. Sci., Pittsburgh, 1992, pp. 60–69.
Tech. Rep. RC 19272 (83907), IBM, 1993.
Tech. Rep. CS96-11, Univ. Ca' Foscari di Venezia, Oct. 1996.
J. ACM 44 (5): 669–696, 1997.Uses a divide and conquer on the edge set of a graph, together with the idea of replacing subgraphs by sparser certificates, to make various dynamic algorithms as fast on dense graphs as they are on sparse graphs. Applications include random generation of spanning trees as well as finding the \(k\) minimum weight spanning trees for a given parameter \(k\).
Finding the k shortest paths.
D. Eppstein.
35th IEEE Symp. Foundations of Comp. Sci., Santa Fe, 1994, pp. 154–165.
Tech. Rep. 94-26, ICS, UCI, 1994.
SIAM J. Computing 28 (2): 652–673, 1998.This paper presents an algorithm that finds multiple short paths connecting two terminals in a graph (allowing repeated vertices and edges in the paths) in constant time per path after a preprocessing stage dominated by a single-source shortest path computation. The paths it finds are the k shortest in the graph, where k is a parameter given as input to the algorithm.
The k shortest paths problem has many important applications for finding alternative solutions to geographic path planning problems, network routing, hypothesis generation in computational linguistics, and sequence alignment and metabolic pathway finding in bioinformatics. Although there have been many papers on the k shortest paths problem before and after this one, it has become frequently cited in those application areas. Additionally, it marks a boundary in the theoretical study of the problem: prior theoretical work largely concerned how quickly the problem could be solved, a line of research that was closed off by the optimal time bounds of this paper. Subsequent work has focused instead on devising efficient algorithms for more complex alternative formulations of the problem that avoid the repeated vertices and other shortcomings of the alternative paths produced by this formulation.
The journal version also includes material from a separate 1995 technical report, "Finding common ancestors and disjoint paths in DAGs".
(Full paper – Graehl implementation – Jiménez-Marzal implementations – Shibuya implementation – Cliff OpenStreetMap demo)
Subgraph isomorphism in planar graphs and related problems.
D. Eppstein.
Tech. Rep. 94-25, ICS, UCI, 1994.
6th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1995, pp. 632–640.
arXiv:cs.DS/9911003.
J. Graph Algorithms and Applications 3 (3): 1–27, 1999.Uses an idea of Baker to cover a planar graph with subgraphs of low treewidth. As a consequence, any fixed pattern can be found as a subgraph in linear time; the same methods can be used to solve other planar graph problems including vertex connectivity, diameter, girth, induced subgraph isomorphism, and shortest paths. A companion paper, "Diameter and treewidth in minor-closed graph families", presents a result announced in the conference version of this paper, that exactly characterizes the minor-closed graph families for which the same techniques apply.
The crust and the beta-skeleton: combinatorial curve reconstruction.
N. Amenta, M. Bern, and D. Eppstein.
Graphical Models & Image Processing 60/2 (2): 125–135, 1998.We consider the problem of "connect the dots": if we have an unknown smooth curve from which sample points have been selected, we would like to find a curve through the sample points that approximates the unknown curve. We show that if the local sample density is sufficiently high, a simple algorithm suffices: form the Delaunay triangulation of the sample points together with their Voronoi vertices, and keep only those Delaunay edges connecting original sample points. There have been many follow-up papers suggesting alternative methods, generalizing the problem to the reconstruction of curves with sharp corners or to curves and surfaces in higher dimensions, etc.
A Möbius-invariant power diagram and its applications to soap bubbles and planar Lombardi drawing.
D. Eppstein.
Invited talk at EuroGIGA Midterm Conference, Prague, Czech Republic, 2012.
Discrete Comput. Geom. 52 (3): 515–550, 2014 (Special issue for SoCG 2013).This talk and journal paper combines the results from "Planar Lombardi drawings for subcubic graphs" and "The graphs of planar soap bubbles". It uses three-dimensional hyperbolic geometry to define a partition of the plane into cells with circular-arc boundaries, given an input consisting of (possibly overlapping) circular disks and disk complements, which remains invariant under Möbius transformations of the input. We use this construction as a tool to construct planar Lombardi drawings of all 3-regular planar graphs; these are graph drawings in which the edges are represented by circular arcs meeting at equal angles at each vertex. We also use it to characterize the graphs of two-dimensional soap bubble clusters as being exactly the 2-vertex-connected 3-regular planar graphs.
Listing all maximal cliques in large sparse real-world graphs.
D. Eppstein, M. Löffler, and D. Strash.
J. Experimental Algorithmics 18 (3): 3.1, 2013 (special issue for SEA).This paper combines our theoretical results on clique-finding algorithms from ISAAC 2010 with our experimental results on the same algorithms from SEA 2011. We show how to list all maximal cliques in graphs of bounded degeneracy in time that is linear in the size of the graph and near-optimal in the degeneracy, and we show that low degeneracy explains the good behavior of the algorithm in our experiments on large real-world social networks.
Forbidden configurations in discrete geometry.
D. Eppstein.
Paul Erdős Memorial Lecture, 29th Canadian Conference on Computational Geometry, Ottawa, Canada, 2017.
Invited talk, 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Tokyo, 2017.
Invited talk, 5th International Combinatorics Conference, Melbourne, Australia, 2017.
Invited talk, Southern California Theory Day, Irvine, California, 2018.
Cambridge University Press, 2018.We survey problems on finite sets of points in the Euclidean plane that are monotone under removal of points and depend only on the order-type of the points, and the subsets of points (forbidden configurations) that prevent a point set from having a given monotone property.
(CCCG talk slides – CCCG talk video – SCTD talk slides – Updates, errata, and reviews)
Counting polygon triangulations is hard.
D. Eppstein.
arXiv:1903.04737.
Proc. 35th Int. Symp. on Computational Geometry, Portland, Oregon, June 2019.
Leibniz International Proceedings in Informatics (LIPIcs) 129, 2019, pp. 33:1–33:17.
Discrete Comput. Geom. 64 (4): 1210–1234, 2020 (special issue for SoCG 2019).Given a polygon with holes, it is #P-complete to determine how many triangulations it has.
Finding relevant points for nearest-neighbor classification.
D. Eppstein.
arXiv:2110.06163.
Proc. SIAM Symp. Simplicity in Algorithms, 2022, pp. 68–78; best paper award winner.The nearest-neighbor classification problem considered here takes as input a training set of points in a Euclidean space, each with a classification from some finite set of classes or colors, and then uses that input to predict the classification of new points as being equal to that of the nearest neighbor in the input training set. A training point is irrelevant when removing it from the training set would produce the same predicted classification for all possible new points that might be queried. We describe how to find all of the relevant points, in polynomial time, using a simple algorithm whose only components are construction of a minimum spanning tree of the training set and the computation of extreme points (convex hull vertices) of geometrically transformed subsets of points. For any constant dimension, with \(k\) relevant points resulting from a training set of \(n\) points, this method can be made to take time \(O(n^2+k^2n)\), using only simple algorithms for the minimum spanning tree and extreme point subroutines. For small dimensions, somewhat better but more complicated bounds are possible.
On the biplanarity of blowups.
D. Eppstein.
arXiv:2301.09246.
Proc. 31st Int. Symp. Graph Drawing and Network Visualization, Palermo, Italy, 2023 (best paper award).
Springer, Lecture Notes in Computer Science 14465 (part I), pp. 3–17.
J. Graph Algorithms & Applications 28 (2): 83–99, 2024.Expanding every vertex of a planar graph to two independent copies can produce a graph of thickness greater than two, disproving a conjecture of Ellen Gethner. We also investigate special cases of this construction for which the thickness is two.
Non-Euclidean Erdős–Anning theorems.
D. Eppstein.
arXiv:2401.06328.
41st International Symposium on Computational Geometry (SoCG 2025), Kanazawa, Japan.
Leibniz International Proceedings in Informatics (LIPIcs) 332, 2025, pp. 46:1–46:15.Non-collinear point sets with integer distances must be finite, for strictly convex distance functions on the plane, for two-dimensional complete Riemannian manifolds of bounded genus, and for geodesic distance on convex surfaces in 3d.