David Eppstein

Professor
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
Email: eppstein@uci.edu

University of California, Irvine
4214 Bren Hall
Mail Code: 3425
Irvine, CA 92697

picture of David  Eppstein

Research
Interests
Graph algorithms and computational geometry
   
URLs Departmental home page
   
Research blog
   
Research
Abstract
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
   
Publications 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.
   
   
Link to this profile http://www.faculty.uci.edu/profile.cfm?faculty_id=4679
   
Last updated 10/26/2007