David Eppstein - Publications

Surveys

• Parallel algorithmic techniques for combinatorial computation.
  D. Eppstein and Z. Galil.
  Ann. Rev. Comput. Sci. 3: 233–283, 1988.
  Invited talk by Z. Galil, 16th Int. Coll. Automata, Languages and Programming, Stresa, Italy, 1989.
  Springer, Lecture Notes in Comp. Sci. 372, 1989, pp. 304–318.

  This survey on parallel algorithms emphasized the use of basic subroutines such as prefix sums, Euler tours, ear decomposition, and matrix multiplication for solving more complicated graph problems.

• Efficient algorithms for sequence analysis.
  D. Eppstein, Z. Galil, R. Giancarlo, and G.F. Italiano.
  International Advanced Workshop on Sequences, Positano, Italy, 1991.
  Sequences II: Methods in Communication, Security, and Computer Science, R.M. Capocelli, A. De Santis, and U. Vaccaro, eds., Springer, 1993, pp. 225–244.
  

  Surveys results on speeding up certain dynamic programs used for sequence comparison and RNA structure prediction.

• Ten algorithms for Egyptian fractions.
  D. Eppstein.
  Mathematica in Education and Research 4 (2): 5–15, 1995.

  Number theory. I survey and implement in Mathematica several methods for representing rational numbers as sums of distinct unit fractions. One of the methods involves searching for paths in a certain graph using a k shortest paths heuristic.

  Also available in HTML and Mathematica notebook formats.

• Mesh generation and optimal triangulation.
  M. Bern and D. Eppstein.
  Tech. Rep. CSL-92-1, Xerox PARC, 1992.
  Computing in Euclidean Geometry, D.-Z. Du and F.K. Hwang, eds., World Scientific, 1992, pp. 23–90.
  Revised version in Computing in Euclidean Geometry, 2nd ed., D.-Z. Du and F.K. Hwang, eds., World Scientific, 1995, pp. 47–123.

  Considers both heuristics and theoretical algorithms for finding good triangulations and tetrahedralizations for surface interpolation and unstructured finite element meshes. Note that the online copy here omits the figures.

• Approximation algorithms for geometric problems.
  M. Bern and D. Eppstein.
  Approximation Algorithms for NP-hard Problems, D. Hochbaum, ed., PWS Publishing, 1996, pp. 296–345.

  Considers problems for which no polynomial-time exact algorithms are known, and concentrates on bounds for worst-case approximation ratios, especially those depending intrinsically on geometry rather than on more general graph theoretic or metric space formulations. Includes sections on the traveling salesman problem, Steiner trees, minimum weight triangulation, clustering, and separation problems.

• Spanning trees and spanners.
  D. Eppstein.
  Tech. Rep. 96-16, ICS, UCI, 1996.
  Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, eds., Elsevier, 1999, pp. 425–461.

  Surveys results in geometric network design theory, including algorithms for constructing minimum spanning trees and low-dilation graphs.

• Quasiconvex programming.
  D. Eppstein.
  Invited talk at DIMACS Worksh. on Geometric Optimization, New Brunswick, NJ, 2003.
  Plenary talk at ALGO 2004, Bergen, Norway, 2004.
  arXiv:cs.CG/0412046.
  Combinatorial and Computational Geometry, Goodman, Pach, and Welzl, eds., MSRI Publications 52, 2005, pp. 287–331.

  Defines quasiconvex programming, a form of generalized linear programming in which one seeks the point minimizing the pointwise maximum of a collection of quasiconvex functions. Surveys algorithms for solving quasiconvex programs either numerically or via generalizations of the dual simplex method from linear programming, and describe varied applications of this geometric optimization technique in meshing, scientific computation, information visualization, automated algorithm analysis, and robust statistics.

  (DIMACS talk slides – ALGO talk slides)

• Selected open problems in graph drawing.
  F. J. Brandenburg, D. Eppstein, M. T. Goodrich, S. G. Kobourov, G. Liotta, and P. Mutzel.
  11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
  Springer, Lecture Notes in Comp. Sci. 2912, 2004, pp. 515–539.

  We survey a number of open problems in theoretical and applied graph drawing.

• Geometry of partial cubes.
  D. Eppstein.
  Invited talk at 6th Slovenian International Conference on Graph Theory, Bled, Slovenia, 2007.

  I survey some of my recent results on geometry of partial cubes, including lattice dimension, graph drawing, cubic partial cubes, and partial cube flip graphs of triangulations.

  (Slides)

• Graph-theoretic solutions to computational geometry problems.
  D. Eppstein.
  Invited talk at the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), Montpellier, France, 2009.
  Springer, Lecture Notes in Comp. Sci. 5911, 2009, pp. 1–16.
  arXiv:0908.3916.

  We survey problems in computational geometry that may be solved by constructing an auxiliary graph from the problem and solving a graph-theoretic problem on the auxiliary graph. The problems considered include the art gallery problem, partitioning into rectangles, minimum diameter clustering, bend minimization in cartogram construction, mesh stripification, optimal angular resolution, and metric embedding.

• Hyperconvexity and metric embedding.
  D. Eppstein.
  Invited talk at Fifth William Rowan Hamilton Geometry and Topology Workshop, Dublin, Ireland, 2009.
  Invited talk at IPAM Workshop on Combinatorial Geometry, UCLA, 2009.

  Surveys hyperconvex metric spaces, tight spans, and my work on Manhattan orbifolds, tight span construction, and optimal embedding into star metrics.

• Regular labelings and geometric structures.
  D. Eppstein.
  arXiv:1007.0221.
  Invited to 22nd Canadian Conference on Computational Geometry (CCCG 2010).
  Invited to Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, 2010.
  Springer, Lecture Notes in Comp. Sci. 6506, 2010, p. 1.
  

  We survey regular labelings for straight-line embedding of planar graphs on grids, rectangular partitions, and orthogonal polyhedra, and the many similarities between these different types of labeling.

  (CCCG talk slides)