David Eppstein
Distinguished Professor, Computer Science
Donald Bren School of Information and Computer Sciences
Donald Bren School of Information and Computer Sciences
B.S., Stanford University, 1984, Mathematics
Ph.D., Columbia University, 1989, Computer Science
Ph.D., Columbia University, 1989, Computer Science
University of California, Irvine
4214 Bren Hall
Mail Code: 3425
Irvine, CA 92697
4214 Bren Hall
Mail Code: 3425
Irvine, CA 92697
Research Interests
Graph algorithms and computational geometry
Research Abstract
Prof. Eppstein has over 400 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
- 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
Publications
D. Eppstein (2018), Forbidden Configurations in Discrete Geometry, Cambridge University Press
D. Eppstein, M. Löffler, and D. Strash (2013), "Listing all maximal cliques in large sparse real-world graphs in near-optimal time", ACM J. Experimental Algorithmics 18: 3.1–3.21
D. Eppstein (1999). "Finding the k shortest paths", SIAM J. Comput. 28(2): 652-673.
M. Bern, D. Eppstein, and J. Gilbert (1994). "Provably good mesh generation", J. Comp. Sys. Sci. 48: 384-409.
Professional Societies
Fellow, Association for Computing Machinery
Fellow, American Association for the Advancement of Science
Link to this profile
https://faculty.uci.edu/profile/?facultyId=4679
https://faculty.uci.edu/profile/?facultyId=4679
Last updated
10/13/2022
10/13/2022