Donald Bren School of Information and Computer Sciences
B.S., Stanford University, 1984, Mathematics
Ph.D., Columbia University, 1989, Computer Science
Phone: (949) 824-6384
Fax: (949) 824-4056
University of California, Irvine
4214 Bren Hall
Mail Code: 3425
Irvine, CA 92697
Graph algorithms and computational geometry
Prof. Eppstein has over 200 publications spanning a broad variety of topics in the design and analysis of algorithms, including
- biological sequence comparison and RNA secondary structure inference
- finite element mesh generation and optimal triangulation
- constructing arrangements of lines and curves
- data structures for maintaining information about changing graphs
- clustering and hierarchical clustering
- listing multiple nearly-optimal solutions to graph optimization problems
- pattern matching in graphs
- nearest neighbor and closest pair queries for geometric data
- computational robust nonparametric statistics
- parametric and bicriterion optimization
- exponential time algorithms for NP-hard problems
- spanning trees and low-distortion approximation of metrics by trees
- graph coloring
- reconstructing curves and surfaces from scattered data points
- graph drawing and information visualization
- folding and unfolding of surfaces
- computational topology
- computational complexity of puzzles and games
- partial cubes and metric embedding of graphs
- color spaces and optimization of color palettes
- quasiconvex optimization and generalized low-dimensional linear programming
- low-memory algorithms for high-bandwidth data streams
D. Eppstein, J.-C. Falmagne, and S. Ovchinnikov (2008). Media Theory: Interdisciplinary Applied Mathematics. Springer-Verlag.
R. Beigel and D. Eppstein (2005).
"3-coloring in time O(1.3289^n)",
J. Algorithms 54(2): 168-204.
D. Eppstein and S. Muthukrishnan (2001). "Internet packet filter management and rectangle geometry", 12th ACM-SIAM Symp. Discrete Algorithms, pp. 827-835.
D. Eppstein (1999). "Finding the k shortest paths", SIAM J. Comput. 28(2): 652-673.
N. Amenta, M. Bern, and D. Eppstein (1998). "The Crust and the beta-skeleton: combinatorial curve reconstruction", Graphical Models and Image Processing 60/2(2): 125-135.
D. Eppstein, Z. Galil, G.F. Italiano, and A. Nissenzweig (1997). "Sparsification: a technique for speeding up dynamic graph algorithms", J. ACM 44(5): 669-696.
M. Bern, D. Eppstein, and J. Gilbert (1994). "Provably good mesh generation", J. Comp. Sys. Sci. 48: 384-409.